使用递归的二叉树平衡检查？

Question

大家好， 我正在尝试了解如何查看二叉树是否平衡。我试图打印出 cout 语句以尝试进一步理解它，但没有运气。

算法的思路是，如果returns -1 则不平衡，如果returns 其他则平衡。

但是我不太明白这个算法到底是如何工作的。但我想知道的几件事是；

int checkBalance(node *root)
{
if (root == NULL) return 0;

int left = checkBalance(root->left);
int right = checkBalance(root->right);
 //cout << "Root: " << root->key << " Left: " << left << ", Right: " << right << endl;

if (left == -1 || right == -1) return -1;
if (abs(left-right) > 1) return -1;

if (left > right) return left+1;
return right+1;
}

我的困惑点在于以下代码行：

if (root == NULL) return 0;
- 当它 return 为 0 时会发生什么，它什么时候达到 0？只是为了防止递归继续访问未知的内存地址，还是 return 数字 0 有任何意义？
if（左>右）return左+1；
- 左边怎么比右边大？在我查看它时，它总是 returns right+1，导致没有任何增量 'left' 因为条件永远不会为真？
int left = checkBalance(root->left);
- 当您以这种方式声明一个 int 时，这意味着什么？这就是让左 > 右的东西吗？

感谢您抽出宝贵的时间阅读，我已经尝试自己研究这个问题，但我很难理解这段代码是如何工作的。

完整代码：http://pastebin.com/raw/VaiUNVdJ（检查案例 6，添加节点的案例 1）

Answer 1

这是基本的BBT检查。它检查子树是否平衡。如果不是，则returns -1；如果是这样，它 return 是深度。

在伪代码中：

如果给定的子树为空，return 0（深度）
在左右子树上递归（检查平衡和深度）
如果任一子树不平衡，return -1
比较左右深度；如果它们相差超过 1，return -1
如果我们到了这里，这棵子树是平衡的。 Return 它的深度。这是两个子树深度中较大的一个，再加上 1。

解决您的具体问题：

此算法 return 树的深度（如果不平衡则为 -1）。空树的深度为 0.
只要左边的树比右边的树深，左边就比右边大。看到这里还有问题吗？
这就是您声明和初始化变量的方式。它与 in left = 0 的语法相同，除了赋值的 RHS 是一个表达式。

这是否足以让您摆脱困境？

让我们采用您提供的节点值，使用根节点为 49、子节点为 48 和 51 的树结构，中缀表示法可能如下所示：

(48, 49, (50, 51, 52))

更严格的形式，

49->left  = 48
49->right = 51
51->left  = 50
51->right = 52
There are no other children

以 root = node 49 开头，我们得到

int left = checkBalance(root->left);    // returns depth of 1
int right = checkBalance(root->right);  // returns depth of 2

现在，left < right，所以最后比较returns right+1, or 3, 也就是正确的树深度。

使用递归的二叉树平衡检查？

Binary Tree Balanced Check Using recursion?

c++

tree

recursion

binary-tree