LeetCode 226. 翻转二叉树：递归思维的入学考试

题目与那个著名的段子

LeetCode 226：翻转二叉树——每个节点的左右子树互换。

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

那个段子：据传一位开发者（Homebrew 作者 Max Howell）面试 Google 被拒，理由是「不会在白板上翻转二叉树」——段子的真假存疑——但它让这道 Easy 题成了「面试必会」的代名词——「简单的题未必简单——它是分层的」——会写的人觉得 trivial、不会写的人无从下手——分水岭在「递归思维」。

递归解：三行代码与「信任」

递归的分解：翻转整棵树 = 翻转左子树 + 翻转右子树 + 交换左右指针：

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left   # 交换
    invert_tree(root.left)                          # 翻转新左子树
    invert_tree(root.right)                         # 翻转新右子树
    return root

「信任递归」的思考方式：「invert_tree(root.left) 会让左子树被完整翻转」——不要展开去追（反转链表篇的递归思想——「假设子调用正确」——只处理当前层的交换——「当前层的工作只有一行：交换」——然后信任两个递归把两边搞定——「递归的简洁性来自『分层职责』：当前层管交换、子层管子树——「不要在脑中展开递归树」是递归思维成熟的标志——「展开追」只会把自己绕晕——验证用「小例子手推」（两层树手推一遍——「小例子验证 + 大例子信任」的两段式。

「交换在递归前还是后」：先交换再递归 vs 先递归再交换——两种都能正确（先交换：递归的是「翻转后的」左右子树——再交换：递归的是「原来的」左右子树——「递归的是子树本身」——子树的内部翻转不受外部指针交换影响——「都正确」的原因：交换只动指针、不动子树内容——「递归的对象是子树的引用」——「引用语义」是树递归的正确性保证——这个细节能答上来，递归才算真懂。

迭代解：BFS 与 DFS 的翻转

迭代版一：BFS 队列。层序遍历（库内 102 题）——「每个节点出队时交换左右」：

from collections import deque

def invert_tree(root):
    if not root:
        return None
    queue = deque([root])
    while queue:
        node = queue.popleft()
        node.left, node.right = node.right, node.left
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)
    return root

迭代版二：DFS 显式栈。栈保存待访问节点——「递归的显式化」（有效括号篇的栈思想——「递归转迭代」的通用手法——「三种遍历方式（递归/BFS/DFS 迭代）都能解这道题」——翻转的「无序性」：每个节点独立翻转、与顺序无关——「操作与遍历顺序无关」是本题的特殊性——对比「层序遍历输出」（顺序就是答案）——「答案与顺序无关的题」遍历方式随便选——「顺序敏感的题」只有一种遍历对——**「判断遍历顺序是否敏感」是树题的第二个思考点。

「为什么这道题还在面试」

考察点的分层：第一层：递归的肌肉记忆（树的题十有八九要递归——「递归三件套」：终止条件（空节点）、当前层操作（交换）、递归调用（左右子树）——「三件套」的完整度——「终止条件优先写」的习惯。第二层：追问的深度——面试官的连环追问——「复杂度」：时间 O(n)（每个节点访问一次）、空间 O(h)（递归栈深度 = 树高——「平衡树 O(log n)、最坏链状 O(n)」——「追问 BFS 解的空间」：O(w)（最大宽度——「空间复杂度取决于数据结构」的对比——「追问迭代版」（会不会写显式栈——「分层考察」是面试的设计——一道 Easy 题挖出递归、遍历、复杂度、迭代化四层能力。第三层：变体的应对——翻转的变体（「只交换值不换指针」（值交换——子树不换——「语义的微妙差异」——「恢复翻转」（翻转两次等于没翻——「操作的对称性」——「变体应对」是「背题」与「理解」的分水岭**。

翻转二叉树的进阶：递归三件套、遍历选择与变体应对

翻转二叉树的进阶：递归三件套、遍历选择与变体应对。「递归三件套」的完整拆解：「套件一：终止条件」——「if not root: return None」——「终止条件优先写」的习惯——「终止条件的完整性」（「空节点」的判断——「单节点也要递归吗」（单节点交换=自己和自己换——「无变化但无害」——「单节点可以不递归」——「终止条件的两个写法」（「if not root」统一 vs「if not root.left and not root.right」叶子终止——「叶子终止」省一层递归——「统一写法」更简洁——「简洁 vs 效率」的微权衡。「套件二：当前层操作」——交换左右指针——「当前层只有一行」——「这一行的位置」（交换在递归前 vs 后——「前 vs 后」——两种都正确——「引用语义」的解释——「指针 vs 引用」在 Python 中的形态（「Python 的对象引用」——「树的节点是引用」——「交换不影响子树内容」——「引用语义」的深入理解——「指针操作」的底层（「树的节点在内存」——「指针的赋值」——「C/Java/Python」的差异——「Python 的简单性」——「指针操作的语言差异」是面试的加分话题。「套件三：递归调用」——左右子树分别递归——「递归的顺序」（先左后右——「顺序影响」（本题无关——「顺序无关」的原因（左右独立——「独立」——「有顺序影响的树题」（中序遍历的输出——「顺序敏感」的题——「遍历顺序即输出顺序」。「遍历方式的选择」——「递归（DFS）」最简洁——「BFS 层序翻转」——「每层交换」——「层序」的遍历——「DFS vs BFS」的选择——「DFS 更简洁」——「BFS 更直观」——「BFS 迭代无栈风险」——「大树的 BFS」——「选择」的依据。「变体的应对」——「变体 1：只翻转值不换指针」——值交换——「值交换 vs 指针交换」——「值交换的对称性」——「变体 2：恢复翻转」——再翻转一次——「操作的对称性」——「两次翻转=恒等」——「对称操作」的性质——「变体 3：只翻转偶数层」——「层级的判断」——「深度+条件」的组合——「翻转的条件化」——「条件翻转」需要知道深度——「前序传深度」——「深度」的下传——「变体 4：翻转子树的部分节点」——「更复杂的条件」——「条件翻转」的泛化——「变体应对的能力」来自对「基础操作的透彻理解」——「基础透了，变体只是加条件」——「变体应对」是「背题」与「理解」的分水岭。「面试的深度追问」：「追问 1：时间复杂度」——O(n)——「为什么」（每个节点访问一次——「追问 2：空间复杂度」——O(h)——「h 的含义」（递归栈深度——「平衡树 O(log n)」——「最坏链状 O(n)」——「追问 3：迭代版」——BFS 队列——「追问 4：能否原地」——已经是原地——「追问 5：层序输出翻转后的树」——「翻转后」的层序——「翻转+遍历」的组合——「追问的深度」体现面试官对你的判断——「每一层追问」都对应一个基础能力——「递归的掌握程度」通过追问暴露。翻转二叉树的进阶总结：递归三件套（终止/操作/递归）+遍历选择（DFS 简洁 vs BFS 无栈）+变体应对（值交换/恢复/条件化）+面试追问（复杂度/迭代/层序）——「翻转二叉树」的教学价值：它是「递归思维」的入学考试——「入学考试」的意义：不是筛选聪明人，是确认每个人都掌握了递归的三件套——「三件套的肌肉记忆」——终止条件优先写、当前层最小化、递归信任子调用——「这三件事写对了，树的递归题就不会错」——「翻转二叉树」之后，你应该能轻松应对：对称树、相同树、最大深度、最小深度、平衡树、合并树——「这些题」全是递归三件套的变奏——「变奏」不需要新思维，只需要新操作——「新操作」写在「当前层」——「这就是树的递归题的全部秘密。

翻转二叉树的面试三问：原地性、镜像关系与「翻转之后」

收尾前回答三个高频问题。「翻转是原地操作吗？返回的是原来的树吗？」——是原地：全程没有新建节点，改的只是每个节点自己的左右指针，返回的 root 与传入的 root 是同一个引用——「原地」的含义就是「不分配新节点、复用旧结构」。与之对照的是「新建一棵翻转树」的写法：递归时逐个 new 节点、原树保持不动——那是复制语义，适合「原树还要用」的场景（比如可视化工具里同时展示翻转前后两棵树）。面试时先声明「这是原地修改」，再补一句「如果要求原树不动，就改成新建节点的复制版」——一句话展示你对「原地 vs 复制」的敏感，这也是工程里深拷贝与浅拷贝的分野。「翻转后的树和原树是什么关系？」——互为镜像，而且这个关系是「对合」：翻转两次等于恒等——由此能推出一道现成的关联题：一棵树对称，当且仅当它与自己的翻转相同，也就是 same(t, invert(t)) 为真——226 与 101（对称二叉树）就这样串成一族：101 的交叉比较，本质是 226 的「判等版」。面试里主动把这层关系讲出来，比孤立背两份代码高一个档次——「题目之间有结构」是刷题者的进阶标志。「能用中序遍历做翻转吗？」——能，但别扭且有坑：中序的处理时机在「左子树遍历完之后」，如果在这个时机交换左右孩子，接下来转向的 curr.right 其实已经变成了「原来的左子树」——不先把引用存进临时变量，就会把同一棵子树处理两遍。更省心的做法是换成后序时机：先递归两边、回来再交换。这道追问真正考的是「你知不知道遍历中修改结构会让遍历计划失效」——交换指针的瞬间，遍历器手里的「下一个节点」可能已经不是你以为的那个——这个意识在链表题（边遍历边改 next）里同样致命。最后补一个工程影子：翻转二叉树对应现实的「镜像布局」——界面从 LTR 语言切到 RTL（阿拉伯语、希伯来语）时，整棵视图树的左右子布局互换，框架做的正是这题的泛化：递归交换每个节点的左右、保持层级不变——简单题的泛化能力，恰是它经久不衰的原因。

小结

翻转二叉树的完整解析：递归三行（交换+两个递归——「信任子调用」的思维方式——当前层只管交换、「引用语义」保证两种交换时机都对）；迭代的自由（BFS/DFS 显式栈都能解——「操作与遍历顺序无关」时遍历随便选）；面试的三层考察（递归三件套的肌肉记忆、复杂度与迭代的追问、变体的应对）；那个段子的启示——「不会翻转二叉树」被拒的故事之所以流传，是因为它戳中了工程师的焦虑：基本功的考察永不过时——递归三件套（终止、操作、递归）写到肌肉记忆——「基本功」的练习方式不是刷难题，是把简单题写到没有任何迟疑。

翻转二叉树是递归思维的入学考试——考的不是聪明，是「你能不能放心地把问题交给子调用」——这种信任一旦建立，树上的一切问题都变成了当前层的几行代码。