[leetcode]Validate Binary Search Tree

经过昨日训练，中序遍历基本会了。所以这个就比较顺利，对二分查找树来说，中序遍历就是递增的。所以遍历一下，遇到反例返回false即可。

public class Solution {
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode n = root;
        int last = Integer.MIN_VALUE;
        while (n != null || !stack.empty()) {
            if (n != null) {
                stack.push(n);
                n = n.left;
            }
            else {
                n = stack.pop();
                // visit n
                if (n.val <= last) return false;
                last = n.val;
                n = n.right;
            }
        }
        return true;
    }
}

另外一种递归解法见此：http://www.cnblogs.com/remlostime/archive/2012/11/16/2772629.html

递归判断，递归时传入两个参数，一个是左界，一个是右界，节点的值必须在两个界的中间，同时在判断做子树和右子树时更新左右界。

Python3，记录上一个visited的值，并递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        prev = [None]
        return self.checkBST(root, prev)
        
    def checkBST(self, root: TreeNode, prev: []) -> bool:
        if root is None:
            return True
        if root.left is not None:
            if not self.checkBST(root.left, prev):
                return False
        if prev[0] is not None and prev[0] >= root.val:
            return False
        prev[0] = root.val
        if root.right is not None:
            if not self.checkBST(root.right, prev):
                return False
        return True