我有以下结构来表示二叉树:
typedef struct node *pnode;
typedef struct node {
int val;
pnode left;
pnode right;
} snode;
树的 Weight 是树的所有节点的 val
参数的总和。当树为空或左子树的权重等于右子树的权重并且每个子树(左和右)都是强平衡时,我们说树是强平衡。我必须编写函数来判断树是否是强平衡的。
我写的代码:
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));
}
上面的函数做得很好,但我注意到它不止一次访问树的节点。是否可以改进(也许通过使用动态规划)只访问树的每个节点一次?
最佳答案
如果 getweight
还告诉您子树是否是强平衡的,您可以将代码简化为单次扫描。
有几种方法可以从函数调用中返回两条信息。如果有一些您知道永远不会是子树权重的返回值(可能是负数),您可以将其用作子树不是强平衡的信号。或者您可以简单地返回两个值:bool
和 int
。 (在 C 语言中,您可以为其中之一使用“out”参数。)或者您可以定义一个具有两个值的复合对象,在 C 语言中为 struct { bool balanced;重量;
。
不管你怎么做,逻辑都是一样的。在下面的伪代码中,我只是假设您可以像在某些语言(例如 C++,但尽管有任何偶然的相似性,但它仍然是伪代码)中一样返回值对:
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 */
}
关于c - 强平衡树 - 改进,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35301119/