奔兼问狗social问题# pets - 心有所宠
x*0
1 楼
The question is:
Check if a binary tree is a valid binary search tree.
I guess I can pass the definition of the binary search tree in this forum. :
-). I know this is a very basic question and have a lot of solutions with O(
N) time complexity and O(1) space complexity.
Since I'm practicing how to use bottom-up traversal skill, Let's restrict
the answer must be bottom-up traversal algorithm.
The following is my idea.
Using "min" and "max" to represent the minimum value of left sub-tree and
maximum value of right sub-tree of the current node. So if the current tree
is a binary search tree, it must obey min < current node < max. We traversal
the tree from bottom to top and update the "min" and "max" every time.
The following is my c code:
int isBSTUtil(struct node* root, int* min, int* max)
{
if(root==NULL)
return 1;
int l = isBSTUtil(root->left, min, max);
int curMin;
if(root->left==NULL)
{
curMin = root->data;
}
else
{
curMin = *min;
}
int r = isBSTUtil(root->right, min, max);
int curMax;
if(root->right==NULL)
{
curMax = root->data;
}
else
{
curMax = *max;
}
*min = curMin;
*max = curMax;
printf("\nMin and Max update: [%d %d]", *min, *max);
return l && r && (root->datadata > (*min));
}
int min = INT_MIN;
int max = INT_MAX;
int mark = isBSTUtil(root, &min, &max);
Can anyone help me verify it? Or provide your own code and then I can learn
from it.
Thanks,
Zhong
Check if a binary tree is a valid binary search tree.
I guess I can pass the definition of the binary search tree in this forum. :
-). I know this is a very basic question and have a lot of solutions with O(
N) time complexity and O(1) space complexity.
Since I'm practicing how to use bottom-up traversal skill, Let's restrict
the answer must be bottom-up traversal algorithm.
The following is my idea.
Using "min" and "max" to represent the minimum value of left sub-tree and
maximum value of right sub-tree of the current node. So if the current tree
is a binary search tree, it must obey min < current node < max. We traversal
the tree from bottom to top and update the "min" and "max" every time.
The following is my c code:
int isBSTUtil(struct node* root, int* min, int* max)
{
if(root==NULL)
return 1;
int l = isBSTUtil(root->left, min, max);
int curMin;
if(root->left==NULL)
{
curMin = root->data;
}
else
{
curMin = *min;
}
int r = isBSTUtil(root->right, min, max);
int curMax;
if(root->right==NULL)
{
curMax = root->data;
}
else
{
curMax = *max;
}
*min = curMin;
*max = curMax;
printf("\nMin and Max update: [%d %d]", *min, *max);
return l && r && (root->datadata > (*min));
}
int min = INT_MIN;
int max = INT_MAX;
int mark = isBSTUtil(root, &min, &max);
Can anyone help me verify it? Or provide your own code and then I can learn
from it.
Thanks,
Zhong
