力扣226题：翻转二叉树 - 递归解法详解

内容简介

本文详细解析了力扣226题"翻转二叉树"的递归解法。通过递归遍历二叉树的每个节点并交换其左右子树，实现了二叉树的完全翻转。文章包含完整注释代码、算法思路讲解和复杂度分析，帮助读者掌握二叉树操作的核心技巧。

算法思路

‌1.递归终止条件‌：当前节点为空时返回

‌2.节点处理‌：交换当前节点的左右子树

‌3.递归调用‌：对左右子树分别进行翻转操作

‌4.返回结果‌：返回翻转后的根节点

代码实现（带详细注释）

class Solution {
public:
    // 递归翻转二叉树的辅助函数
    void invert(TreeNode* root) {
        if(!root) {  // 递归终止条件：当前节点为空
            return;
        }
        // 交换当前节点的左右子树
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        
        // 递归翻转左右子树
        invert(root->left);
        invert(root->right);
    }
    
    // 翻转二叉树的主函数
    TreeNode* invertTree(TreeNode* root) {
        invert(root);  // 调用辅助函数翻转整棵树
        return root;   // 返回翻转后的根节点
    }
};

复杂度分析

‌时间复杂度‌：O(n)，需要访问二叉树中的每个节点

‌空间复杂度‌：O(h)，递归栈的深度取决于二叉树的高度h

最坏情况下(树退化为链表)：O(n)

平衡二叉树情况下：O(log n)

优化方向

‌迭代实现‌：可以使用栈或队列实现非递归版本

‌尾递归优化‌：某些编译器可以优化尾递归

‌并行处理‌：对于大型树可以考虑并行处理左右子树

总结

翻转二叉树是二叉树操作的经典问题，通过递归交换每个节点的左右子树，可以简洁高效地实现二叉树的翻转。理解这种解法有助于掌握二叉树遍历和递归算法的核心思想。