力扣226题翻转二叉树：解题思路与C++实现详解
理解题目要求与示例分析
力扣226题"翻转二叉树"的核心要求是将每个节点的左右子树位置互换。给定二叉树[4,2,7,1,3,6,9]，翻转后应该得到[4,7,2,9,6,3,1]。这道题考察的是对二叉树结构的理解和基本操作能力。在开始编码前，我们需要明确几个关键点：什么是二叉树？如何表示二叉树节点？翻转操作具体指什么？理解这些基础概念是解决本题的前提。
递归解题思路详解
递归是解决二叉树问题的常用方法。对于翻转二叉树，递归思路非常直观：从根节点开始，先翻转左子树，再翻转右子树，交换当前节点的左右子树。这个思路符合分治思想(divide and conquer)，将大问题分解为小问题解决。递归的终止条件是遇到空节点(nullptr)，这时直接返回即可。这种自上而下的递归方式时间复杂度为O(n)，空间复杂度为O(h)，其中h是树的高度。
迭代解法思路对比
除了递归，我们还可以使用迭代方法解决这个问题。迭代通常借助栈(stACk)或队列(queue)来实现。对于翻转二叉树，层序遍历(BFS)是一个不错的选择：从根节点开始，将每个节点的左右子节点交换，将其子节点入队。这种方法同样能达到O(n)的时间复杂度，但空间复杂度在最坏情况下会达到O(n)。迭代解法的优势在于避免了递归可能导致的栈溢出问题。
C++实现代码与逐行注释
struct TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode invertTree(TreeNode root) {
// 递归终止条件：当前节点为空
if(!root) return nullptr;
// 递归翻转左子树
TreeNode left = invertTree(root->left);
// 递归翻转右子树
TreeNode right = invertTree(root->right);
// 交换当前节点的左右子树
root->left = right;
root->right = left;
return root;
}
};边界条件与特殊情况处理
编写健壮的代码需要考虑各种边界条件。对于翻转二叉树，我们需要处理以下几种特殊情况：空树(直接返回nullptr
)、只有根节点的树(返回自身
)、单边倾斜的树(如所有节点只有左子树)。还需要注意内存管理，特别是在实际应用中要避免内存泄漏。在C++中，如果题目要求不能修改原树，则需要先创建树的深拷贝(deep copy)再进行翻转操作。
前面提到的递归和迭代解法在时间复杂度上都是O(n)，因为每个节点都会被访问一次。空间复杂度方面，递归解法取决于递归栈的深度，即树的高度O(h)；而迭代解法在最坏情况下(完全不平衡树)需要O(n)的额外空间。对于优化，可以考虑尾递归优化(tail recursion)或使用Morris遍历等不需要额外空间的方法，但这些方法实现起来较为复杂，对于本题而言，简单的递归或迭代解法已经足够高效。
翻转二叉树是理解递归和树操作的经典例题。通过本文的详细解析，我们学习了递归和迭代两种解题思路，掌握了C++的具体实现，并分析了各种边界条件和算法复杂度。这道题虽然简单，但它很好地展示了分治思想在树问题中的应用，是学习更复杂树算法的基础。建议读者在理解本文内容后，尝试自己实现迭代解法，并思考如何扩展这个问题，比如如何按层打印翻转后的树。
原创内容 转载请注明出处
