226. 翻转二叉树

Origin: LeetCode 226

题目描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1： 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

示例 2： 输入：root = [2,1,3] 输出：[2,3,1]

示例 3： 输入：root = [] 输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

我的解法

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return root
 
    const dfs = (node: TreeNode | null): TreeNode | null => {
        if (!node) return null;
        const left = dfs(node.left);
        const right = dfs(node.right);
        node.left = right;
        node.right = left;
        return node;
    };
 
    return dfs(root);
}

用的是后序：先递归翻完左右子树内部，再把翻好的两棵子树互换挂上。与”先交换再递归”（前序）殊途同归——交换的是引用，顺序不影响结果。

小冗余：外层 if (!root) return root 可以删掉，dfs 的空判断已覆盖空树。

解题思路（草稿）

递归——标准解法

每个节点：左右子树交换，然后对交换后的子树递归。

function invertTree(root: TreeNode | null): TreeNode | null {
    if (!root) return null
    ;[root.left, root.right] = [root.right, root.left]
    invertTree(root.left)
    invertTree(root.right)
    return root
}

递归的本质：翻转整棵树 = 翻转左子树 + 翻转右子树 + 交换两棵子树的位置。 三步顺序其实无所谓——先交换再递归、先递归再交换都对，因为交换的是引用，左右子树内部怎么翻不受外部影响。

和 104 的对比

同样是树上的递归，两题的递归函数形状不同：

	104 最大深度	226 翻转
返回值	number（子树深度）	TreeNode（翻转后的子树根）
递推	max(左, 右) + 1	交换 + 递归
修改原树	不修改	原地修改
后序/前序	后序（先知道子树深度才能 +1）	都行（交换和递归无依赖）

104 的返回值必须先拿到左右结果才能算，天然是后序。226 交换引用和递归互不依赖，前序后序都行——这也说明递归顺序不是背出来的，是由数据依赖关系决定的。

趣闻

这道题是 Homebrew 作者 Max Howell 的著名梗：他去 Google 面试被这道题挂了，发推说 “Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.”——白板算法的荒诞一面。

复杂度

• 时间：O(n)，每个节点交换一次
• 空间：O(h)，递归栈 = 树高，最坏 O(n)

关联

• 树 - 树的题型总览
• 104. 二叉树的最大深度 - 递归返回值形状的对照组