翻转二叉树 图解题解

翻转二叉树到底要翻什么

题目要求把一棵二叉树变成它的镜像：每个节点的左子树和右子树互换位置，返回翻转后的根。注意「每个节点」三个字——不只是根节点换一次，树里任何一层的任何节点，它的左右孩子都要对调。只在根上换一次，得到的树深层结构仍是原样，不是镜像。

为什么翻转二叉树天然适合递归

镜像有一个漂亮的自相似结构：整棵树的镜像 = 根不动，把原来的右子树的镜像挂到左边，把原来的左子树的镜像挂到右边。也就是说，「翻转一棵树」这个大问题，恰好等于「交换根的两个孩子」加上两个一模一样但更小的问题——翻转左子树、翻转右子树。问题的定义本身就是递归式的，代码照着定义抄下来就是答案。

于是函数只有三件事：空节点直接返回 None（递归出口）；交换 root.left 和 root.right；再对新的左右孩子各调一次自己。不需要任何额外数据结构，也不需要记录状态。

交换的是指针，不是节点里的值

一个常见的错误是只交换左右孩子节点里存的数值。这在孩子是叶子时碰巧看不出问题，可一旦孩子下面还挂着后代，只换值等于把两棵子树的「门牌号」换了、里面的房间没搬——孩子各自的子孙还留在原来那一侧，结构就错了。正确做法是交换 left、right 两个指针：一次赋值就把整棵子树连同它所有后代整体搬到另一边，后代内部的翻转交给递归去完成。

先交换再递归，还是先递归再交换

两种顺序结果完全一样。原因是「交换某个节点的左右孩子」这个操作只动这个节点自己的两个指针，跟别的节点互不干扰；只要保证树里每个节点都被交换恰好一次，先处理谁都行。所以前序、后序甚至层序遍历都能做这道题——用队列或栈遍历，每弹出一个节点就交换它的孩子再把孩子入队，就是等价的迭代写法。真正不能省的是两件事都要做：只递归不交换，树纹丝不动；只交换根不递归，深层没翻。

复杂度怎么算，哪里容易翻车

时间 O(n)：n 个节点每个恰好访问一次，每次只做常数次指针操作。空间 O(h)：递归栈的深度等于树高 h，平衡树是 O(log n)，退化成链的最坏情况是 O(n)。

最容易翻车的点是漏写空判断：递归走到叶子的孩子时传进来的是 None，不先返回就会对空对象取 left 而崩溃。另外空树本身也是合法输入，if not root: return None 一行同时兜住这两种情况。

Python

def invertTree(root):
    if not root:
        return None            # ① 空节点直接返回
    root.left, root.right = \
        root.right, root.left  # ② 交换左右孩子
    invertTree(root.left)      # ③ 递归翻左子树
    invertTree(root.right)     #   递归翻右子树
    return root

C++

TreeNode* invertTree(TreeNode* root){
    if(!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

Java

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = root.right;   // 交换
    root.right = tmp;
    invertTree(root.left);    // 递归左
    invertTree(root.right);   // 递归右
    return root;
}