226.翻转二叉树

翻转一棵二叉树 输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解答

先递归，再交换

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(root == null) {
        return root
    }
    // 递归压栈到底
    invertTree(root.left)
    invertTree(root.right)
    // 执行交换
    const temp = root.left
    root.left = root.right
    root.right = temp
    return root
};

或者可以先交换左右子树，然后递归翻转子树

const invertTree = (root) => {
  if (root == null) { // 遍历到null节点时，不用翻转，直接返回它本身
    return root;
  }
  // swap
  const temp = root.left;
  root.left = root.right;
  root.right = temp;
  // 内部的翻转交给递归去做
  invertTree(root.left);
  invertTree(root.right);
  return root;
};

BFS即迭代做法：

用层序遍历的方式去遍历二叉树。根节点先入列，然后出列，出列就 “做事”，交换它的左右子节点（左右子树）。并且让左右子节点（左右子树）入列，往后，这些子节点（子树）会出列，也被翻转。直到队列为空，就遍历完所有的节点（子树），翻转了所有子树，即翻转了整个二叉树。

const invertTree = (root) => {
  if (root == null) {
    return root;
  }
  const queue = [];   // 维护一个队列
  queue.push(root);   // 初始推入第一层的root
  
  while (queue.length) {
    const cur = queue.shift(); // 出列的节点

    const temp = cur.left;     // 交换出列节点的左右子树
    cur.left = cur.right;
    cur.right = temp;

    if (cur.left) {            // 入列考察，因为要继续翻转它们
      queue.push(cur.left);
    }
    if (cur.right) {
      queue.push(cur.right);
    }
  }

  return root; // 返回交换后的节点
};