如何检查完整的二叉树是否值平衡

Question

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

Answer 1

您可以对树进行后序遍历，对每个子树求和，当返回（每个子树的）根时，评估两个子树是否具有相同的权重。

类 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);
}

在哪里

< Li > < code > Node get left(Node *)返回一个指针，该指针指向一个表示参数左侧子节点的节点 < Li > < code > Node getRight(Node *)返回一个指针，该指针指向表示参数的右子节点的节点 < Li > < code > int getValue(Node *)返回给定节点的值

这个想法是做一个后序遍历，向左求和所有子级的值，向右求和，然后：

1. 验证正确性-如果不正确，整个树的答案是否定的，并将其设置为res
2. 将当前节点的两个总和相加，并将其返回给父节点