This question is almost same as the one in CtCi. The only difference is that Leetcode considers
"The left subtree of a node contains only nodes with keys less than the node's key.", while CtCi think "less than or equal to" is also okay. Whatever the difference is, the code remains almost the same.
When I attacked this problem at first, I thought that the max value of left subtree should be less than or equal to root.val, and the min value of right subtree larger than. And all the subtrees should follow this pattern. Although I tried many times to keep track of the leftMax of left subtree, and rightMin of right subtree, both of these 2 get changed when some leaves are traversed. This is really frustrating, since this should be very easy to solve.
Finally, I turn to CtCi for help. After understanding its answer, I put the code into Leetcode. Accepted. But nothing exciting, I need more practices.
The CtCi's answer is very good. Short, understandable, brief.
Now let me talk a little bit about its code.
The most brilliant part is to pass root.val as rightMin. Actually, leftMax and rightMin are lower and upper limits. Now, please check the comments below:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
return checkBST(root,null,null);
}
public boolean checkBST(TreeNode root, Integer leftMax, Integer rightMin){
if(root == null) return true;
if((leftMax != null && root.val <= leftMax) ||
(rightMin!=null && root.val >= rightMin))// if rightMin NOT null, root is left of the node(val = rightMin)
// Thus, if we take CtCi's definition, this condition should be (rightMin!=null && root.val > rightMin)
// since left child could be equal to root
return false;
if( checkBST(root.left,leftMax,root.val) &&// check left subtree, now let root.val be upper limit
checkBST(root.right,root.val,rightMin)) //check right subtree, now let root.val be lower limit
return true;
else return false;
}
}
Hello, welcome to Yizhe's Blog. I am Yizhe Liu, graduated from University of Arizona, with Master degree, major in Electrical and Computer Engineering. Actually, I am software guy. In my blog, many posts are about the Leetcode questions. I will post my ideas and implementations, which are accepted by Leetcode. If you have different opinions, please leave comment. I am happy to discuss with you. So lets start rocking them!!!
Thursday, May 29, 2014
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment