如何找到二叉搜索树中每个节点的余额？

Question

我目前有一个检查整个二叉树是否平衡的函数。（这是伪代码）

int bchecker (node * root)
{
  if null, return 1, otherwise continue;

  rightsubheight = height(node->right)
  leftsubheight = height(node->left)

  if ((absolute difference between right and left is <= 1) AND (bchecker(node->left) == 1) and AND (bchecker(node->right) == 1), then return 1

  otherwise return 0
}

基本上，如果函数处于平衡状态，则返回1，否则返回0。这是计算高度的函数：

int height (node * root)
{
  if null, return 1, otherwise continue

  return 1 + max(height(node->left), height(node->right));
  // max is just a function that finds the higher value between the two 
}

但是，我想计算每个节点的余额，并将其存储在该节点的相应结构中。我该怎么办？

Answer 1

嗯，这是我要做的最简单的形式：

1）分配内存以存储每个节点的结果。由于存储的是1和0，因此只需要一个内存块，其大小等于节点数。

2）以标准方式遍历树并从每个节点调用函数。将结果存储在数组中，然后递增到下一个空槽。

完成后，您将拥有一个带有1和0的2D数组。

然后可以通过多种方式对其进行优化。您的伪代码应该能够处理此问题。只需在每个节点上遍历被称为bchecker的对象即可。