递归如何在二叉树中填充SubTree值？

Question

我正在研究Leetcode问题110。平衡二叉树，我也不知道在执行递归时子树值是如何被填充的。在看了几个解决方案之后，下面是我在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?

我知道递归会穿过树的左边和右边。我不知道如何通过递归计算子树值。谁能解释一下吗？

Answer 1

我画了这个图表，可以帮助你可视化。当递归展开时，传递给父级的值将以红色加下划线。每个节点将检查其左、右子节点报告的值的差异。如果在任何节点上，diff > 1，则不平衡。

另外，在每个节点上，它获取左和右子节点报告的值的最大值，将1添加到它(对于当前级别)并发送到其父节点。

左边的树是平衡的，而右边的不是。

​

​

Answer 2

有几件事值得注意：

• 树高是离叶子最深的地方。
• 自然，父母的身高是最高的孩子+1的高度。
• 如果树的所有子树的高度相差小于或等于1，则树是平衡的。
• 函数名treeHeight令人困惑。应该称为balancedTreeHeightOrMinusOne

因此，如果balancedTreeHeightOrMinusOne不是-1，则树是平衡的；它是通过检查(递归)其子树的balancedTreeHeightOrMinusOne来计算的。如果它们之间的差异太大，那么返回-1这是不平衡的。否则，返回它最高的孩子的高度加上一个。

Answer 3

基本情况是：

if(!root) return 0;

所以我们知道函数如何返回0。

下一个案例是这个：

return Math.max(leftSubTree, rightSubTree) + 1;

我们从基本情况中了解到，leftSubTree和rightSubTree都可以是0(因为它们表示递归调用的返回值)，因此这里有一个返回1的情况。所以现在我们已经看到，无论是0还是1都可以返回。

但是，这个return也可以得到一个最大值，即1，所以返回2！所以任何正整数都会变成一个可能的返回值。

现在看一看这句话：

if(Math.abs(leftSubTree - rightSubTree) > 1) return -1; 

正如我们看到的那样，leftSubTree和rightSubTree可以是任何无符号整数(因为它们是递归调用返回的值)，绝对值可以是任何无符号整数，因此在某些情况下，这种条件是真的。现在我们有了第一种情况，返回的值是-1 (这里的意思是：“它不平衡”)。

唯一有待解释的陈述是：

if(leftSubTree === -1 || rightSubTree === -1) return -1;

在前面的例子中，我们看到了递归调用确实可以返回-1。这里说，如果任何一个子树不平衡，那么这个树也是不平衡的。