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

19339201706

内容简介

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

算法思路

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

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

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

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

代码实现（带详细注释）

1. class Solution {
   
2. public:
   
3.     // 递归翻转二叉树的辅助函数
   
4.     void invert(TreeNode* root) {
   
5.         if(!root) {  // 递归终止条件：当前节点为空
   
6.             return;
   
7.         }
   
8.         // 交换当前节点的左右子树
   
9.         TreeNode* tmp = root->left;
   
10.         root->left = root->right;
    
11.         root->right = tmp;
    
12.         
    
13.         // 递归翻转左右子树
    
14.         invert(root->left);
    
15.         invert(root->right);
    
16.     }
    
17.    
    
18.     // 翻转二叉树的主函数
    
19.     TreeNode* invertTree(TreeNode* root) {
    
20.         invert(root);  // 调用辅助函数翻转整棵树
    
21.         return root;   // 返回翻转后的根节点
    
22.     }
    
23. };

复制代码

C++

复杂度分析

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

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

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

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

优化方向

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

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

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

总结

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

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