x*****0 发帖数: 452 | 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->data<(*max) && root->data > (*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 | c***s 发帖数: 192 | 2 用两个边界来判断的思路是对的,不过你的codes写得复杂了点。
下面是我写的:
public class ValidateBinarySearchTree {
public boolean isValidBST(TreeNode root, int min, int max) {
if(root == null) return(true);
if(root.val <= min || root.val >= max) return(false);
return(isValidBST(root.left, min, root.val) &&
isValidBST(root.right, root.val, max));
}
public boolean isValidBST(TreeNode root) {
return(isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
}
:
O(
tree
【在 x*****0 的大作中提到】 : 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
| x*****0 发帖数: 452 | 3 谢谢啊~
比我的code简洁多了。
感觉你的code是top bottom traveral。
是这样的吗?:-)
【在 c***s 的大作中提到】 : 用两个边界来判断的思路是对的,不过你的codes写得复杂了点。 : 下面是我写的: : public class ValidateBinarySearchTree { : public boolean isValidBST(TreeNode root, int min, int max) { : if(root == null) return(true); : if(root.val <= min || root.val >= max) return(false); : return(isValidBST(root.left, min, root.val) && : isValidBST(root.right, root.val, max)); : } : public boolean isValidBST(TreeNode root) {
| z***2 发帖数: 66 | 4 蠻短的
【在 c***s 的大作中提到】 : 用两个边界来判断的思路是对的,不过你的codes写得复杂了点。 : 下面是我写的: : public class ValidateBinarySearchTree { : public boolean isValidBST(TreeNode root, int min, int max) { : if(root == null) return(true); : if(root.val <= min || root.val >= max) return(false); : return(isValidBST(root.left, min, root.val) && : isValidBST(root.right, root.val, max)); : } : public boolean isValidBST(TreeNode root) {
| l*****a 发帖数: 14598 | 5 return 带括号?不常见
为什么不能等于min/max?
【在 c***s 的大作中提到】 : 用两个边界来判断的思路是对的,不过你的codes写得复杂了点。 : 下面是我写的: : public class ValidateBinarySearchTree { : public boolean isValidBST(TreeNode root, int min, int max) { : if(root == null) return(true); : if(root.val <= min || root.val >= max) return(false); : return(isValidBST(root.left, min, root.val) && : isValidBST(root.right, root.val, max)); : } : public boolean isValidBST(TreeNode root) {
|
|