LC226　翻转二叉树¶

简单通过率 82.5%python3核心代码模式二叉树样例通过牛客 AC树深度优先搜索广度优先搜索二叉树

一句话

在每个节点处交换左右孩子指针，遍历一遍即可，顺序无所谓。

解题思路¶

这题考什么¶

「翻转」是把整棵树沿竖直轴做镜像。看上去要搬动整棵子树，其实只需要一个局部操作：在每个节点处交换它的左右指针。交换 node.left 与 node.right 时，两棵子树是整体搬家的 —— 子树内部的相对关系此刻还没处理，但只要保证每个节点都被交换过一次，所有层的镜像就同时完成了。

因为每个节点的操作互不干扰（交换只碰 node 自己的两个字段，不读孩子的内容），遍历顺序完全自由：前序、后序、层序都行。这里用显式栈做深度优先搜索（DFS），弹出即交换，再把两个孩子压回去继续。

示例 1 的 [4,2,7,1,3,6,9]：4 处交换后孩子是 (7, 2)，7 处交换后是 (9, 6)， 2 处交换后是 (3, 1)，层序读出来就是 [4,7,2,9,6,3,1]，与样例一致。

数据规模与复杂度¶

节点数在 [0, 100]，节点值在 [-100, 100]。每个节点入栈出栈各一次、交换一次，时间 O(n)；栈里同时存在的节点不超过树高，空间 O(h)，链状树退化到 O(n)。这个量级递归也跑得动（深度最多 100，低于 CPython 默认的 1000 层上限），选迭代是为了跟本专题里 LC98、LC124 那些必须迭代的题统一口径。

坑在哪¶

返回的是原来的 root，不是新建的树。这题是原地修改，交换的只是指针，节点对象自始至终没有换过。
空树要返回 None，不能返回 []。判题按声明的返回类型 TreeNode 编码，空树序列化出来才是 []；函数本身必须返回 None。题面示例 3 给的正是空树。
压栈用交换前还是交换后的孩子，结果一样。压回去的是同一对节点对象，只是先后不同，而每个节点最终都会被弹出、被交换一次。真正不能省的是「每个节点都要被访问到」这一条。
空孩子照压不误，弹出后统一跳过。若改在压栈处逐个判空，左右两条分支各要写一遍，反而更容易漏掉一处。

参考实现¶

solutions/leetcode/LC226/sol.py
from typing import List, Optional


class Solution:
    def invertTree(self, root: "Optional[TreeNode]") -> "Optional[TreeNode]":
        # 栈里是「还没交换过左右孩子」的节点；root 为 None 时首轮就被跳过
        stack = [root]
        while stack:
            node = stack.pop()
            # 空子树没有可交换的指针，直接跳过；压栈处因此不必判空
            if node is None:
                continue
            # 唯一的操作：就地交换两个孩子指针，本层的镜像即告完成
            node.left, node.right = node.right, node.left
            # 两棵子树各自还要在内部继续镜像，压回栈里等着被处理
            stack.append(node.left)
            stack.append(node.right)
        # 原地修改，返回的仍是传进来的那个根
        return root

LC226 翻转二叉树¶