强平衡树 - 改进

Question

我有以下结构来表示二叉树：

typedef struct node *pnode;
typedef struct node {
   int val;
   pnode left;
   pnode right;
} snode;

树的

Weight 是树的所有节点的 val 参数的总和。我们说树是 strongly balanced 当它是空的或左子树的权重等于右子树的权重并且每个子树（左和右）是强平衡的。我必须编写函数来判断树是否是强平衡的。

我写的代码：

int getWeight(pnode tree)
{
   if(! tree)
      return 0;
   return getWeight(tree->left) + getWeight(tree->right)
            + tree->val;
} 

bool isStronglyBalanced(pnode tree)
{
   if(! tree)
      return true;

   int wL, wR;
   wL = getWeight(tree->left);
   wR = getWeight(tree->right);

   if(wL != wR)
      return false;
   return (isStronglyBalanced(tree->left) && isStronglyBalanced(tree->right));
}

上面的函数工作得很好，但我注意到它不止一次访问树的节点。是否可以改进（也许通过使用动态规划）只访问树的每个节点一次？

Answer 1

如果getweight也告诉你子树是否是强平衡的，你可以将代码简化为单次扫描。

有几种方法可以从函数调用中 return 获取两条信息。如果有某个 return 值，您知道它永远不会成为子树的权重（可能是负数），您可以将其用作子树不是强平衡的信号。或者您可以简单地 return 两个值：bool 和 int。（在 C 语言中，您可以为其中之一使用 "out" 参数。）或者您可以定义一个具有两个值的复合对象，在 C 语言中为 struct { bool balanced; int weight; }.

不管你怎么做，道理都是一样的。在下面的伪代码中，我只是假设您可以像在某些语言（例如 C++，但尽管有任何偶然的相似性，但它仍然是伪代码）中一样可以 return 对值：

pair<bool, int> get_weight(tree) {
  if (!tree) return {true, 0};
  balanced, weight_left = get_weight(tree->left);
  if (!balanced) return {false, 0};      /* Returned weight doesn't matter */
  balanced, weight_right = get_weight(tree->right);
  return {balanced && weight_left == weight_right,
          2 * weight_right + tree->val}; /* weight_left == weight_right */
}

强平衡树 - 改进

Strongly balanced tree - improvement

c

algorithm

binary-tree