我想实现一个函数 isOk(Node*, int&)
检查BST的每个节点是否遵守了以下属性。
-左右两棵子树的高度可以相差最多一级
一个例子可以是: -它的左右子树的高度最多可以相差1级。
这是我写的函数
bool isOk(Node* tree, int& maxH)
{
//if leaf, property is respected
if(!tree->left_ && !tree->right_) return true;
//otherwise
int hL = 0;
int hR = 0;
bool propL = isOk(tree->left_, hL);
bool propR = isOk(tree->right_, hR);
if(propL) hL++;
if(propR) hR++;
if(hL - hR => -1 && hL - hR <= 1) {
maxH = max(hL, hR);
return true;
}
else return false;
}
我们假设一个Node结构是这样的:
struct Node
{
Node* left_;
Node* right_;
int label_;
//no constructor or destructor, this is not the focus
};
最初我写的这部分:
/*...*/
int hL = 0;
int hR = 0;
bool propL = isOk(tree->left_, hL);
bool propR = isOk(tree->right_, hR);
if(propL) hL++;
if(propR) hR++;
/*...*/
是这样写的:
int hL = height(tree->left_);
int hR = height(tree->right_);
bool propL = isOk(tree->left_, hL);
bool propR = isOk(tree->right_, hR);
其中的函数 height(Node*)
是。
int height( Node* tree)
{
if(tree== NULL) return 0;
int leftH = 0;
int rightH = 0;
leftH = height(tree->left_);
rightH = height(tree->right_);
return 1 + max(leftH, rightH);
}
现在,复杂的... height
如果我没有说错的话,应该是O(n)。所以,如果在我的 isOk
函数,其整体复杂度应该会大大增加吧?
话说回来,我试着追踪每一个子树的高度,每次递增 hL
和 hR
每当 isOk
.
我这是做错了什么吗?请纠正我哪里错了。
谢谢你
可以有 isOk
归还 pair<bool, int>
其中 bool
表示返回该值的节点是否遵循该属性,并且 int
代表它在树上的高度。
假设 pair<boor, int> propL, propR
分别是当前节点的左、右子节点返回的值,那么当前节点将满足上述属性,如果 propL->first == true && propR->first == true && (int)abs(propL->second-propR->second) <= 1
. 然后这个值和当前节点的高度(等于 max(propL->second, propR->second) + 1
)将被返回给当前节点的父节点。