从子树的平衡证明树是平衡的

Question

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

这本书的示例解决方案（复制如下）假设从节点发出的树是平衡的，如果（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);
}

Answer 1

既然是你要求的，这里有更多关于归纳法的内容：

https://en.wikipedia.org/wiki/Well-founded_relation

忘记你所知道的关于归纳的一切，这里是真正的东西。如果我们有一些关系，R被认为是有根据的，当且仅当没有无限下降链x1，x2，x3，... x1 R x2，x2 R x3等等。（“下降”，因为人们在想

例如

有良好的关系，你有

（适用于所有x:（适用于所有y:x R y-

换句话说，这足以表明所有最小元素都有关系。R有一些性质，然后表明如果所有比x小的元素都满足P，那么x也满足P。

特例是你可能知道的归纳：

（P（0）

对于有限树，子树关系（显然）是有充分基础的，因此我们可以（实际上让我们使用传递闭包，使证明更短。它仍然是有充分基础的）：

基本情况：（叶子，这些是微小的wrt子树关系）叶子有0个孩子是平衡的，微不足道

归纳：假设所有子树（和它们的子树等等）都是平衡的，根节点是平衡的，所有节点都是平衡的，没有剩下不平衡的节点（看到我在这里做了什么吗？）

如果我们还注意到平衡意味着子树是平衡的，我们可以在不使用传递闭包的情况下做到这一点。然后我们可以说，使直接子树平衡意味着它们的所有子树也平衡，我们回到了我的证明。

Answer 2

平衡二叉树是指左右两个子树的总深度相差不超过一[1]。这里，给出的解决方案是递归的，首先检查子对象本身是否平衡，然后检查父对象是否平衡。它通过检查子对象的左、右子树的深度来实现这一点，如果它们之间的深度相差atmost 1，则返回max（left\u depth，right\u depth）1。如果不是，则返回-1。然后，该算法对整个树继续执行此操作。如果深度在任意点为-1（表示子树未平衡），则子树的总体深度将返回为-1。最后，只需检查树的总深度是否为-1：如果为-1，则树不平衡，否则为-1。

以下是归纳形式的算法：

>

基本情况

叶节点-平凡平衡，具有0个子节点。它返回1，因为深度将包括子节点数（0）和节点本身。

归纳案例

中间节点，如果子节点处于平衡状态，则该节点将处于平衡状态，左侧子节点的深度与右侧子节点的深度相差atmost 1。如果平衡，它将返回max（left\u depth，right\u depth）1，表示树的总深度，包括节点本身。如果不平衡，只需返回-1。

最后

根节点，与归纳情况一样检查，但如果平衡，则整个树是平衡的，总深度为max（left\u depth，right\u depth）1，其中left\u depth和right\u depth表示左/右子树相对于根节点的深度。

这里可以找到之前提出的一个问题，该问题涵盖了BST编码的几个非常有趣的方面。

Answer 3

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

顺便说一句，在整个函数中，将root替换为currode，以明确例程如何递归地应用于树中的每个节点，而不仅仅是根节点。