跳到主要内容

LeetCode 226. 翻转二叉树

本节目标

递归翻转左右子树，再交换当前节点的两个孩子指针。

这是路径状态与结构变换中“返回变换后子树根”的母题。翻转后的每个节点都要让原来的左子树变成右子树，原来的右子树变成左子树。

查看 LeetCode 原题

题意与关键边界​

空树翻转后仍为空。翻转不是只交换根节点的两个孩子：每一层的左右关系都必须改变，因此测试应比较保留空节点标记的层序结构，而不只比较节点值集合。

朴素思路与瓶颈​

可以用队列逐层访问并交换每个节点的孩子。该做法正确，但需要额外队列空间。递归把“翻转一棵子树”的定义直接写成函数，结构更贴合题意。

变换后子树根不变量​

invertTree(root) 的返回值始终是“以 root 为根且已完全翻转”的子树根。先递归取得翻转后的左、右子树根，再将它们交叉写回 root.left 与 root.right，最后返回 root。

这里局部变量 left、right 保存的是递归完成后的结果。它们让交换动作不会丢失任何一棵子树，同时使函数合同在每一层保持一致。

正确性依据​

空节点满足翻转定义。对非空节点，归纳假设保证递归返回的 left 与 right 分别是原左右子树的完整翻转；把它们交换后，当前根的左右关系被翻转，且两棵子树内部也已翻转。因此返回的 root 正是整棵原子树的翻转结果。

代码实现​

C++17
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

源码在两个递归调用完成后才交换指针，返回值就是当前根。这使调用者既能得到变换后根节点，也能直接观察原对象已经被原地改写。

复杂度分析​

每个节点访问一次，时间复杂度为 O(n)。除递归栈外不创建与节点数同级的容器，额外空间为 O(h)，其中 h 是树高。

边界与易错点​

  • 空指针必须直接返回空，避免访问不存在的孩子。
  • 只交换根节点会漏掉更深层的左右关系。
  • 测试不能只比较前序序列或值集合；不同形状可能拥有相同的这些结果。
  • 若改成先交换再递归，也必须确认两个递归调用访问的是交换后的正确子树；本题选择先得到两棵递归结果，语义更直观。

模式迁移​

镜像比较、对称树判断也会同时访问成对的左右位置，但它们只读取结构，不改写指针。需要构造一棵独立镜像树时，递归应新建节点并返回新根，而不是修改原树。