1

我正在解决“Cracking the Coding Interview”中的以下问题：实现一个函数来检查二叉树是否平衡。平衡树是这样一棵树，使得任何节点的两个子树的高度都不会相差超过 1。

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

3 回答 3

0

平衡二叉树是左右子树的总深度相差不超过一[1]的树。这里提出的解决方案是递归的，首先检查孩子自己是否平衡，然后检查父母是否平衡。它通过检查孩子的左右子树的深度来做到这一点，如果它们之间的深度最多相差 1，则返回max(left_depth,right_depth)+1. 如果不是，则返回-1. 然后该算法对整个树继续此操作。如果深度在任意点为 -1（表明子树不平衡），则子树的总深度返回为 -1。最后，只需检查树的总深度是否为 -1：如果是，则树不平衡，否则，它是。

这是归纳形式的算法：

  • 基本情况

    叶节点 - 平凡平衡，有 0 个子节点。它返回 1，因为深度将包括子节点的数量 (0) 以及节点本身。

  • 归纳案例

    一个中间节点，如果孩子平衡，就会平衡，并且左孩子的深度与右孩子的深度最多相差1。如果平衡，它返回max(left_depth,right_depth) + 1，表示树的总深度，包括节点本身. 如果不平衡，只需返回-1。

  • 最后

    根节点，像归纳情况一样检查，但如果平衡，则整个树是平衡的，总深度为max(left_depth,right_depth) + 1，其中left_depth和right_depth表示左/右子树相对于根节点的深度。

可以在此处找到以前提出的 SO 问题，该问题涵盖了编写 BST 的几个非常有趣的方面。

于 2015-05-25T09:09:59.553 回答
0

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

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

于 2015-05-25T09:15:16.937 回答
0

既然你要求它，这里有更多关于归纳的信息：

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

忘记你所知道的关于感应的一切，这是真实的。如果我们有一些关系 R，当且仅当不存在无限下降链 x1, x2, x3, ... 与 x1 R x2, x2 R x3 等等时，我们说 R 是有根据的。（“降序”是因为人们在考虑 < 数字）

例如，< 在自然数上是有根据的，但在实数上却不是。

有了有根据的关系，你就有了

(对于所有 x : (对于所有 y : x R y -> P(y)) -> P(x)) <-> 对于所有 x : P(x)

换句话说，足以证明所有最小元素都可以。R 有一些性质，然后证明如果所有小于某个 x 的元素都满足 P，那么 x 也满足。

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

(P(0) & for all n: P(n) -> P(n+1)) -> for all n: P(n) （这里有充分根据的关系是后继函数）

对于有限树，子树关系（显然）是有根据的，所以我们可以这样做（实际上让我们使用传递闭包，使证明更短。它仍然是有根据的）：

基本情况：（叶子，这些是最小的 wrt 子树关系）具有 0 个孩子的叶子是平衡的，很简单

归纳：假设所有子树（及其子树等）都是平衡的，并且根节点是平衡的，所有节点都是平衡的，没有剩下可能不平衡的节点（看看我在这里做了什么？）

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

于 2015-06-24T19:52:22.453 回答