题目

解法：递归翻转

思路

核心思想是自顶向下递归地交换每个节点的左右子节点，逐层完成整棵树的翻转。

对于任意节点，先交换其左右子节点，再递归翻转这两个子树。递归终止条件为空节点直接返回。根据数学归纳法，若左右子树均已正确翻转，则当前节点交换后其子树也必然正确翻转。每个节点仅被访问一次，交换操作是原子性的，因此不会遗漏任何节点，最终整棵树被完全翻转。

• Step 1: 若当前节点为空，直接返回
• Step 2: 使用 std::swap 交换当前节点的左右子节点
• Step 3: 递归调用 invertTree 翻转左子树（原右子树）
• Step 4: 递归调用 invertTree 翻转右子树（原左子树）
• Step 5: 返回当前节点

复杂度

• 时间复杂度: $O(n)$，其中 $n$ 为节点数，每个节点仅被访问一次。
• 空间复杂度: $O(h)$，其中 $h$ 为树的高度，递归栈空间消耗。最坏情况 $O(n)$，平均 $O(\log n)$。

代码

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root) {
            std::swap(root->left, root->right); 
            invertTree(root->left);           
            invertTree(root->right);           
        }
        return root;
    }
};