c - 如何判断一棵完全二叉树是否值平衡

Question

如何判断给定的一个数组表示的完全二叉树是否为值平衡二叉树？我所说的值平衡是指，如果对于每个节点，左侧节点的整数值之和等于右侧值的总和。什么是类C算法？
很容易找出有子节点的索引。但是我无法开发递归计算每个节点总和的逻辑。总和还需要以这样一种方式计算，即特定节点下方的左子树的所有节点的总和将等于它的右手对应节点，并以类似的方式向下挖掘。怎么可能使用数组？

Answer 1

你可以做一个post order traversal对每个子树求和，然后返回到(每个子树的)根，评估两个子树是否具有相同的权重。

类 C 伪代码:

res = 1; //global variable, can also be used as sending pointer to res instead
int verifySums(Node* root) {
   if (root == null) return 0;
   int leftSum = verifySums(getLeft(root));
   int rightSum = verifySums(getRight(root));
   if (leftSum != rightSum) res = 0;
   return leftSum + rightSum + getValue(root);
}

在哪里

• Node getLeft(Node*) 正在返回一个指向表示参数的左 child
• Node getRight(Node*) 正在返回一个指向表示论点的右 child
• int getValue(Node*) 正在返回给定节点的值

这个想法是做一个后序遍历，对左边所有 child 的值求和，对右边求和，然后:

1. 验证正确性——如果不是，则整棵树的答案是否定的，并将其设置在res中。
2. 将两个和+当前节点相加，返回给parent。