平衡二叉树：不是看根，是每个节点都要过安检

怎样从“判断树是否平衡：每个节点 abs(leftHeight − rightHeight) ≤ 1，且子树也要平衡。”推导出 二叉树 · 后序 DFS · -1 哨兵，并证明每次状态变化都不会漏掉答案？

中心结论：后序 DFS 返回高度；子树不平衡则返回 -1 向上传播；check(root) != -1 即 true。

判断一棵树是不是平衡二叉树。平衡二叉树的定义是：树中每个节点都满足左右两个子树的高度差 <= 1 的这个条件。

在本站主例中，判断树是否平衡：每个节点 abs(leftHeight − rightHeight) ≤ 1，且子树也要平衡。

算法最终需要得到或观察：平衡 true / 不平衡 false。

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

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

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 递归栈、左右高度、diff、-1 哨兵传播。
3. 3转移每一步按照 后序 DFS 返回高度；子树不平衡则返回 -1 向上传播；check(root) != -1 即 true。
4. 4收尾读取 平衡 true / 不平衡 false。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：递归栈、左右高度、diff、-1 哨兵传播。

根据定义判断即可，计算树的高度是第 104 题。

后序 DFS 返回高度；子树不平衡则返回 -1 向上传播；check(root) != -1 即 true。

执行过程中持续维护：递归栈、左右高度、diff、-1 哨兵传播。

正确性依赖以下不变量：每个节点都要满足 |leftHeight − rightHeight| ≤ 1。；-1 是哨兵值，不是高度，收到即向上传播。

面试时可以压缩为：后序 DFS：递归返回子树高度，不平衡返回 -1 哨兵；left 或 right 为 -1 则直接传 -1；否则检查 diff，超过 1 返回 -1，否则 max(left,right)+1。时间 O(n)，空间 O(h)。

落到当前题，执行机制可以压缩为：后序 DFS 返回高度；子树不平衡则返回 -1 向上传播；check(root) != -1 即 true。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入判断树是否平衡：每个节点 abs(leftHeight − rightHeight) ≤ 1，且子树也要平衡。 因为：后序 DFS 返回高度；子树不平衡则返回 -1 向上传播；check(root) != -1 即 true。
2. 2后序返回高度叶子高度为 1。 因为：深度 = 1 + 子树较高者。
3. 3结点 9 深度 2DFS 记录当前层。 因为：根到该结点边数 = 深度。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5结点 20 深度 2DFS 记录当前层。 因为：根到该结点边数 = 深度。
6. 6结点 15 深度 3DFS 记录当前层。 因为：根到该结点边数 = 深度。
7. 7最大深度 3扫描结束。 因为：O(n) DFS。
8. 8收尾与复杂度平衡 true / 不平衡 false。 因为：时间 O(n) · 空间 O(h)，最坏 O(n)，平衡树 O(log n)。后序 DFS 返回高度；子树不平衡则返回 -1 向上传播；check(root) != -1 即 true。

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

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

func isBalanced(root *TreeNode) bool {
	if root == nil {
		return true
	}
	leftHight := depth(root.Left)
	rightHight := depth(root.Right)
	return abs(leftHight-rightHight) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

func depth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return max(depth(root.Left), depth(root.Right)) + 1
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="max-depth", values=[3,9,20,null,null,15,7]
    //    期望：平衡 true / 不平衡 false。
    //
    // 2. 失败 / 未命中
    //    检查：只算根左右高不够，子树内部可能已不平衡。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC104 深度；LC543 直径
}

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

1. 1题意判断树是否平衡：每个节点 abs(leftHeight − rightHeight) ≤ 1，且子树也要平衡。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化后序 DFS 返回高度；子树不平衡则返回 -1 向上传播；check(root) != -1 即 true。
4. 4证明每个节点都要满足 |leftHeight − rightHeight| ≤ 1。；-1 是哨兵值，不是高度，收到即向上传播。
5. 5复杂度时间 O(n)，空间 O(h)，最坏 O(n)，平衡树 O(log n)