8. 翻转二叉树

翻转一棵二叉树。

输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

二叉树后序遍历：

// 将整棵树的节点翻转
const invertTree = function invertTree(root) {
  if (!root) return null;
  [root.left, root.right] = [root.right, root.left];
  invertTree(root.left);
  invertTree(root.right);
  return root;
}

命令式写法

const mirrorTree = function mirrorTree( root) {
  if (!root) return null;
  [root.left, root.right] = [mirrorTree(root.right), mirrorTree(root.left)];
  return root;
}

函数式写法

const mirrorTree = function mirrorTree( root) {
  if (!root) return null;
  return Tree(node.value, mirrorTree(node.right), mirrorTree(node.left));
}

BFS

var invertTree = function(root) {
  if(!root) return root;
  const q = [root];
  while(q.length) {
    const node = q.shift();
    // 交换左右子树
    [node.left, node.right] = [node.right, node.left];    
    if(node.left) q.push(node.left);
    if(node.right) q.push(node.right);
  }
  return root;
};