226. 翻转二叉树

[Geekhyt]

原题链接

Google：我们 90% 的工程师都用你写的软件（Homebrew），但你没法在白板上翻转二叉树，所以翻滚吧，蛋炒饭。

原推截图，至今仍在。 Max Howell 当年吐槽之后 LeetCode 马上加入了这道题。

会了这道题，是不是我们也可以超越世界级大牛了？(狗头保命)

书归正传

首先明确，所谓二叉树的翻转需要满足以下两点：

1.它的左右子树要交换位置。
2.并且左右子树内部的所有子树或是结点都要进行交换位置。

递归

1.从根节点开始，递归的对树进行遍历。
2.从叶子结点开始进行翻转。
3.左右子树都已经翻转后，交换两棵子树的位置即可完成全部的翻转。

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    invertTree(root.left)
    invertTree(root.right)
    const temp = root.left
    root.left = root.right
    root.right = temp
    return root
}

• 时间复杂度: O(n)
• 空间复杂度: O(n)

当然你也可以将上面的 2，3 两个步骤颠倒执行，也就是先交换两棵子树的位置，再对其内部进行翻转。

const invertTree = function(root) {
    if (root === null) return null // 递归终止条件
    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 null;
  const queue = [root];
  while (queue.length) {
    const cur = queue.shift();
    [cur.left, cur.right] = [cur.right, cur.left];
    if (cur.left) queue.push(cur.left);
    if (cur.right) queue.push(cur.right);
  }
  return root;
}

[yuetong3yu]

Max Howell 也太惨了，被疯狂鞭尸。。