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

Question

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

Answer 1

你可以对树做一个post order traversal，对每个子树求和，当回到（每个子树的）根时，评估两个子树是否具有相同的权重。

C-like伪代码：

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*) 是 return 指向表示节点的指针 参数的左边child
• Node getRight(Node*) 是 return 指向表示节点的指针 参数的右边child
• int getValue(Node*) 是 return 给定节点
的值

想法是做一个post-order遍历，将所有children的值向左求和，向右求和，然后：

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