二叉树递归如何填充子树值？LeetCode 110题求解疑惑

AI 小北

2026-8-15

理解LeetCode 110. 平衡二叉树的递归逻辑

我正在解决LeetCode的110. Balanced Binary Tree问题，对递归过程中子树值的填充方式感到困惑。参考若干解决方案后，得到了如下JavaScript代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    return treeHeight(root) !== -1;
};

function treeHeight(root){
    if(!root) return 0;
    const leftSubTree = treeHeight(root.left);
    const rightSubTree = treeHeight(root.right);
    if(leftSubTree === -1 || rightSubTree === -1) return -1; // how can recursion lead to either subtree being -1? At this point I don't know how this can be true other than "that's just how recursion works"
    if(Math.abs(leftSubTree - rightSubTree) > 1) return -1; // how are the values of either subtree even obtained here?
    return Math.max(leftSubTree, rightSubTree) + 1; // same as the previous question. how do either subtree even get values?
}

我试图理解以下代码行：

if(leftSubTree === -1 || rightSubTree === -1) return -1; // how can recursion lead to either subtree being -1? At this point I don't know how this can be true other than "that's just how recursion works"
    if(Math.abs(leftSubTree - rightSubTree) > 1) return -1; // how are the values of either subtree even obtained here?
    return Math.max(leftSubTree, rightSubTree) + 1; // same as the previous question. how do either subtree even get values?

我明白递归会遍历树的左侧和右侧，但不清楚递归是如何计算出子树值的，能否有人对此进行解释？

递归逻辑详解

这个treeHeight函数的核心是同时完成两个任务：计算子树的高度，以及判断子树是否平衡。它用返回-1表示当前子树不平衡，返回非负整数表示子树的实际高度。

1. 递归的终止条件

当root为null（空节点）时，返回0——空树的高度定义为0，这是递归的“终点”，所有子树的高度计算都会从这里开始回溯。

2. 深度优先的递归遍历

对于任意非空节点，函数会先递归计算左子树的高度leftSubTree，再递归计算右子树的高度rightSubTree。这个过程是深度优先的：比如会先一路挖到最左侧的叶子节点，再逐步向上回溯，依次计算每个节点的子树高度。

3. 为什么会返回-1？

第一个判断if(leftSubTree === -1 || rightSubTree === -1) return -1：如果左/右子树已经返回-1，说明这个子树本身已经是不平衡的。既然子树不平衡，那么当前节点所在的整棵树肯定也不平衡，直接向上返回-1，不用再做后续计算，这是一种提前终止的优化。
第二个判断if(Math.abs(leftSubTree - rightSubTree) > 1) return -1：如果左右子树的高度差超过1，说明当前节点的子树不符合平衡二叉树的要求，返回-1标记不平衡。

4. 子树高度的计算

如果以上两个判断都不触发，说明当前子树是平衡的，那么它的高度就是左右子树高度的最大值 + 1——加1是因为当前节点本身要算一层高度。

举个实际例子理解

假设我们有一棵平衡二叉树：

递归执行过程：

计算节点9的左右子树：都是空节点，返回0。高度差为0，所以节点9的高度是max(0,0)+1=1。
计算节点15和7的左右子树：都是空节点，各自返回1。
计算节点20的左子树（15，返回1）和右子树（7，返回1），高度差0，所以节点20的高度是max(1,1)+1=2。
计算根节点3的左子树（9，返回1）和右子树（20，返回2），高度差1，所以根节点的高度是max(1,2)+1=3。最终treeHeight返回3，不是-1，所以isBalanced返回true。

再看一棵不平衡的树：