Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
这题的话用递归非常简短，覃超昨天直播说，BST一定要注意，是左子树所有的节点都比root小，右子树所有节点逗比root大，说再忘了把头割下来当球踢。。
递归可以让你避免把头当球踢。另外，递归是要多用的，不要逃避。
这题注意 return recursion(root.left , min , root.val) && recursion(root.right , root.val , max);
这句话不要把参数中的root.val写成root.left.val或者root.right.val.
递归
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
return recursion(root, Long.MIN_VALUE , Long.MAX_VALUE);
}
private boolean recursion(TreeNode root , long min , long max ){
if (root == null ) return true;
if (root.val<= min || root.val >= max) return false;
return recursion(root.left , min , root.val) && recursion(root.right , root.val , max);
}
迭代
明天写一下迭代方法。
Mar 25th
下午去了奥森跑10公里。现在来写迭代方法。
看到leetcode的solution里面有个人系统地讲解了：
https://leetcode.com/problems/validate-binary-search-tree/#/solutions。
先是复习了Binary Tree Inorder Traversal这道题里的用stack模拟递归的做法，没毛病：
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
然后，这人给出了230. Kth Smallest Element in a BST 这道题的类似iteration方法：
非常的genius，basicly只换了一行：
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}
最后给出了valid bst这题的解法，我自己也敲了一遍，发现：
不能直接定义一个int pre = -1 , 因为树的节点可以是小于零的。
也不能定义成MIN_VALUE，leetcode有testcase就是单个的MIN_VALUE。
所以要定义一个TreeNode类型的pre，把第一个pop出来的node加进去。
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre != null && root.val <= pre.val) return false;
pre = root;
root = root.right;
}
return true;
}
另，下午在奥森迷路了。。体验有点不好啊，景色也比玄武湖差很多。不过看见了很棒的樱花还是桃花的景色。
23：24PM @ JD
