检查二叉树是否平衡

Question

我正在处理检查平衡二叉树高度的问题，并找到了一个类似的教程

if (height of left subtree == -1)
return -1.
public boolean isBalanced(TreeNode root) {
if (root == null){
return true;
}
return height(root) != -1;

}
int height(TreeNode node){

`if (node  == null){`

return 0;
}

int left = height(node.left);

int right = height(node.right);

int bf = Math.abs(left- right);

if (bf > 1 || left == -1 || right == -1){

return -1;

}

return Math.max(left,right)+1;

}

所以，我想知道在什么情况下，二叉树的左子树的高度会是-1？谢谢

我看了一遍教程，但没有正确解释。

Answer 1

考虑一个树。它有一个根和一个孩子在左边。它左边的孩子只有左边的孩子，没有右边的孩子，依此类推

R
/
C0
/
C1
/
C2
/
C3

Height是用根R调用的。现在根R在其左子项C0和右子项(NULL(上调用Height。C0对C1这样做，然后C1对C2做同样的事情，以此类推

所以我们将从C3到C2再到C1进行计算，因为递归就是这样执行的。

在你的函数高度(C3(中，我们现在称之为高度(C3->左(和高度(C3->右(。两者都为NULL。它们的左和右=0。Height(C3(返回1。作为

(Math.max(left,right)+1; => Math.max(0,0)+1; => 1)

现在对于函数调用height(C2)

left = Height(C2->left) i.e. C3
//hence left = 1;
right = Height(C2->right) i.e. NULL
//hence right = 0;
bf = Math.abs(left-right); => Math.abs(1-0); => 1

仍然所有条件都是假的，我们返回：

Math.max(left,right)+1; => Math.max(1,0)+1; => 2

现在让我们来看看height(C1)

left = height(C1->left) i.e. height(C2)
//left = 2
right = height(C1->right) i.e. height(NULL)
//right = 0

现在，

bf = Math.abs(left-right); => bf = Math.abs(2-0); => bf = 2

由于bf>现在为1，则执行if条件并返回-1。

现在，对于height(C0)

left = height(C0->left); => height(C1)
left = -1 //this is where you get height = -1

现在，从这一点开始，由于条件的原因，所有的回报都将是-1。说这棵树不平衡。