由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - check if a binary tree is a valid binary search tree
相关主题
help: leetcode "Recover Binary Search Tree" -- 附代码为啥有两个case不对??Binary Tree Maximum Path Sum
Find the node with given value in binary tree in in-orderBinary Tree Maximum Path Sum
Leetcode bst max path-----is this solution correct?construct a binary tree from in-order and level-order trav
弱问:leetcode里Convert Sorted List to Binary Search Tree再问个C++的基础问题(in order traversal)
请教大家一个问题:Maximum Height (Depth) of a Binary Tree Using PreOrder Traversal判断是不是binary search tree-leetcode
[leetcode] Maximum Depth of Binary Tree问个G家店面题完全二叉树
leetcode Runtime error : Flatten Binary Tree to Linked List一道在线题
问一个题目这个inorder traversal 有错嘛,为什么leetcode 总报memory limit exceed?
相关话题的讨论汇总
话题: max话题: min话题: int话题: root话题: tree
进入JobHunting版参与讨论
1 (共1页)
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) {

1 (共1页)
进入JobHunting版参与讨论
相关主题
这个inorder traversal 有错嘛,为什么leetcode 总报memory limit exceed?请教大家一个问题:Maximum Height (Depth) of a Binary Tree Using PreOrder Traversal
Flatten Binary Tree to Linked List的recursive解法[leetcode] Maximum Depth of Binary Tree
leetcode交了钱的能share一下题么?leetcode Runtime error : Flatten Binary Tree to Linked List
问tree的iterative traversal问一个题目
help: leetcode "Recover Binary Search Tree" -- 附代码为啥有两个case不对??Binary Tree Maximum Path Sum
Find the node with given value in binary tree in in-orderBinary Tree Maximum Path Sum
Leetcode bst max path-----is this solution correct?construct a binary tree from in-order and level-order trav
弱问:leetcode里Convert Sorted List to Binary Search Tree再问个C++的基础问题(in order traversal)
相关话题的讨论汇总
话题: max话题: min话题: int话题: root话题: tree