手帐 Blog

主题

复盘 · LC 226 翻转二叉树 ​

题目 ​

题意 ​

把一棵二叉树左右子树整体对调（每个节点的左右孩子互换），返回新根（通常仍是原根）。

  • 空树返回 null。
  • 要递归/迭代地处理整棵树，不是只换根的左右一次。

涉及算法 ​

标签一句话
DFS 递归先翻转左右子树，再交换当前左右指针
BFS层序遍历时对每个节点交换左右

教程对照：17 · 二叉树递归经典。

评价我的解法 ​

思路正确：递归翻转，用临时变量交换。

我的代码（摘自 226-翻转二叉树/index.js）：

javascript
var invertTree = function (root) {
  if (!root) {
    return root;
  }
  const tmp = invertTree(root.left);
  root.left = invertTree(root.right);
  root.right = tmp;
  return root;
};

评价：

  1. 能 AC：空树直接返回；先拿到翻转后的左子树，再赋翻转后的右到 left，最后把暂存赋给 right——交换语义对。
  2. 可读性略绕：tmp 存的是「已翻转的左子树根」，而不是「原 left 指针」。更直白的写法是：先递归翻转左右，再 swap(root.left, root.right)，面试口述更顺。
  3. 复杂度：时间 O(n)，空间 O(h)。

小结：结果对；若想口述更清楚，改成「先翻转子树，再交换指针」两步。

最佳题解 ​

javascript
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) return null;
  invertTree(root.left);
  invertTree(root.right);
  const tmp = root.left;
  root.left = root.right;
  root.right = tmp;
  return root;
};
  • 时间 O(n)，空间 O(h)。
  • 为何更清晰：递归职责只负责「子树已翻转」，交换只动当前节点指针，不把「交换」和「返回值赋值」缠在一起。

关联题目 ​

题为何相关
101. 对称二叉树镜像判断 vs 主动翻转
100. 相同的树成对递归比较
104. 二叉树的最大深度同一套递归骨架

一句话带走 ​

翻转二叉树：每个节点左右互换，子树递归做完——和「对称树」是同一镜像心智。