java - 从子树的平衡性证明树是平衡的

我正在解决“破解编码采访”中的以下问题：实现一个函数来检查二叉树是否平衡。平衡树是这样一种树，使得任何节点的两个子树的高度永远不会相差一个以上。

本书的示例解决方案（在下面复制）假定，如果（a）节点的左右子树是平衡的，则从节点发出的树是平衡的； （b）节点本身是平衡的。我想了解为什么会这样？满足以上两个条件如何证明从节点发出的整个树是平衡的？

谢谢

public static boolean isBalanced(TreeNode root)
{
    if (checkHeight(root)==-1)
        return false;
    return true;
}


public static int checkHeight(TreeNode root)
{
    //base case
    if (root == null)
        return 0;

    //is left subtree balanced
    int leftHeight = checkHeight(root.leftChild);

    if (leftHeight == -1)
        return -1;

    //is right subtree balanced
    int rightHeight = checkHeight(root.rightChild);

    if (rightHeight == -1)
        return -1;

    //is current node balanced
    int heightDiff = leftHeight - rightHeight;

    if (Math.abs(heightDiff) > 1)
        return -1;

    return (Math.max(leftHeight, rightHeight) + 1);
}

最佳答案

这是递归的应用程序–例程计算要检查的节点的左和右子树的高度，并同时递归验证子树。如果发现任何节点不平衡，则返回-1；如果可以，则返回子树的高度。子树高度的比较决定了当前节点是否平衡。

顺便说一句，在整个root函数中用currnode替换checkHeight()，以使例程清楚地将例程递归地应用于树中的每个节点，而不仅仅是树的根。

关于java - 从子树的平衡性证明树是平衡的，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30434681/