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

Aug 10
http://www.cnblogs.com/springfor/p/3889729.html