LeetCode 226. 翻转二叉树 (Invert Binary Tree)解题思路这道题的核心在于递归Divide and Conquer。翻转整棵树本质上就是将树中每一个节点的左右子树进行交换。我们可以采用后序遍历的思想自底向上来解决确定终止条件如果当前节点为空root nullptr说明已经到达叶子节点的下方直接返回 nullptr。递归翻转左子树调用 invertTree(root-left)得到翻转后的左子树用临时变量 left 接收。递归翻转右子树调用 invertTree(root-right)得到翻转后的右子树用临时变量 right 接收。交换左右子树将当前节点的 left 指针指向翻转后的 rightright 指针指向翻转后的 left。返回当前节点将处理完毕的当前节点返回给上一层。复杂度分析时间复杂度O(N)。其中 N 为二叉树的节点数。我们会遍历二叉树中的每一个节点对每个节点而言交换其左右子树的时间复杂度为 O(1)因此总时间复杂度为 O(N)。空间复杂度O(H)。其中 H 为二叉树的高度。空间复杂度取决于递归调用栈的深度。在最坏情况下树退化为链表空间复杂度为 O(N)在最好情况下树完全平衡空间复杂度为 O(log N)。知识点说明通过这道题我们可以巩固以下几个核心知识点二叉树的结构与指针操作在 C 中二叉树通常由结构体/类构成包含数据域val和指针域left, right。易错点在交换节点时不能直接写 root-left root-right; root-right root-left;。因为第一行赋值后原本的 root-left 就被覆盖丢失了。必须像图中代码一样使用临时变量 left 和 right 提前保存递归结果。递归的三大要素这道题是理解递归的绝佳案例明确函数的作用invertTree(root) 的作用是翻转以 root 为根的树并返回新的根节点。寻找终止条件 root nullptr。推导递推公式 当前节点的左子树 翻转后的右子树当前节点的右子树 翻转后的左子树。后序遍历后序遍历的顺序是左 - 右 - 根。在代码中表现为先递归处理 root-left 和 root-right最后再处理当前 root 的交换逻辑。