翻转二叉树

怎样从“把树变成镜像：对每个结点交换它的左右孩子(指针),不是改值。”推导出 二叉树 · 递归镜像，并证明每次状态变化都不会漏掉答案？

中心结论：递归:先 swap(root.Left, root.Right),再翻转两棵子树,nil 直接返回。

"经典"的反转二叉树的问题。

在本站主例中，把树变成镜像：对每个结点交换它的左右孩子(指针),不是改值。

算法最终需要得到或观察：每个结点左右孩子互换,整树镜像翻转完成。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 调用栈逐层下钻到 nil 再回收,返回翻转后的新根。
3. 3转移每一步按照 递归:先 swap(root.Left, root.Right),再翻转两棵子树,nil 直接返回。
4. 4收尾读取 每个结点左右孩子互换,整树镜像翻转完成。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：调用栈逐层下钻到 nil 再回收,返回翻转后的新根。

还是用递归来解决，先递归调用反转根节点的左孩子，然后递归调用反转根节点的右孩子，然后左右交换根节点的左孩子和右孩子。

递归:先 swap(root.Left, root.Right),再翻转两棵子树,nil 直接返回。

执行过程中持续维护：调用栈逐层下钻到 nil 再回收,返回翻转后的新根。

正确性依赖以下不变量：翻的是 left/right 指针,不是结点值。；每个结点都交换一次左右孩子,只换根只翻第一层。

面试时可以压缩为：对每个结点 swap 左右孩子再递归翻两棵子树,终止条件 root==nil。时间 O(n) 每点访问一次,空间 O(h) 栈深=树高,最坏 O(n)。

落到当前题，执行机制可以压缩为：递归:先 swap(root.Left, root.Right),再翻转两棵子树,nil 直接返回。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入把树变成镜像：对每个结点交换它的左右孩子(指针),不是改值。 因为：递归:先 swap(root.Left, root.Right),再翻转两棵子树,nil 直接返回。
2. 2递归交换左右子树先交换再递归。 因为：交换后子树也需翻转。
3. 3交换 4 的左右孩子左右指针交换。 因为：局部交换 + 递归 = 全局镜像。
4. 4交换 7 的左右孩子左右指针交换。 因为：局部交换 + 递归 = 全局镜像。
5. 5交换 2 的左右孩子左右指针交换。 因为：局部交换 + 递归 = 全局镜像。
6. 6翻转完成所有结点处理完。 因为：O(n)。
7. 7递归交换左右子树先交换再递归。 因为：交换后子树也需翻转。
8. 8收尾与复杂度每个结点左右孩子互换,整树镜像翻转完成。 因为：时间 O(n) · 空间 O(h)。递归:先 swap(root.Left, root.Right),再翻转两棵子树,nil 直接返回。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	invertTree(root.Left)
	invertTree(root.Right)
	root.Left, root.Right = root.Right, root.Left
	return root
}

func main() {
    // 1. 主例
    //    输入：mode="invert", values=[4,2,7,1,3,6,9]
    //    期望：每个结点左右孩子互换,整树镜像翻转完成。
    //
    // 2. 失败 / 未命中
    //    检查：只换 root 的左右孩子就结束,子树内部没翻。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC101 对称；LC114 展开
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意把树变成镜像：对每个结点交换它的左右孩子(指针),不是改值。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化递归:先 swap(root.Left, root.Right),再翻转两棵子树,nil 直接返回。
4. 4证明翻的是 left/right 指针,不是结点值。；每个结点都交换一次左右孩子,只换根只翻第一层。
5. 5复杂度时间 O(n)，空间 O(h)