1 
int cntHeight(TreeNode *root) {
    if(root == NULL) return 0;
    int l = cntHeight(root->left);
    int r = cntHeight(root->right);
    if(l < 0 || r < 0 || abs(l-r) > 1) return -1;
    else  return max(l, r) + 1;
}

bool isBalanced(TreeNode *root) {
    return cntHeight(root) >= 0;
}

我在 C 中找到了这个解决方案来检查二叉树是否平衡。但是，我很难想象这个算法是如何完全工作的。出于这个原因，有两件事我不确定。

  1. 算法是否在树的中间而不只是边上递归？
  2. 我注意到 onlymax(1, r)被调用，我们不需要找到min吗？

此外，您将如何开发这样的算法？我不知道如何想出这样的解决方案..

4

2 回答 2

3

  1. 是的，它也在树的中间递归。它检查每个节点的左侧和右侧，其中自然包括中间。

  2. 为什么需要分钟？您对最大深度 = 高度感兴趣。注意max(l, r)不是max(1, r)（愚蠢的Ls）

  3. 你从小处着手开发它。考虑一棵由单个节点组成的树，它应该返回什么？然后再添加一层。还有一个。你会经常发现一层的解依赖于上一层的解。这就是递归的用武之地。然后你必须考虑如果函数调用自身会发生什么；它什么时候会停止调用自己？这称为基本情况（在本例中为if(root == null)）。如果它没有停止，您将得到一个堆栈溢出。

于 2013-09-13T03:38:06.060 回答
1

魔法发生在 cntHeight 函数中。它将树的一部分作为参数，如果该部分为空，则返回 0，如果不平衡则返回 -1，否则返回深度。

为此，它首先通过调用自身来获取其两个子树（左和右）的深度。如果其中一个子树不平衡，则整个树不平衡，因此它立即返回 -1。如果其中一个子树比另一个深 2，则该树也是不平衡的，因此它返回 -1（这就是abs(l-r) > 1检查的内容）

在最后一行，函数计算传递树的深度。max这是根节点的较深子树的深度（因此是）+ 1。

我想说开发这样的算法的主要成分是经验。您看到的算法越多，您对可用方法的感觉就越多。

于 2013-09-13T03:42:30.433 回答