Binary Search Tree

二叉搜索树的特点：
左子树所有节点都比node小，右子树所有节点都比node大
中序遍历为递增序列。

230. Kth Smallest Element in a BST

疑问：为什么定义全局变量时加上static就出错，不加就通过了？

class Solution {
    private int count = 0;
    private int result = 0;
    public int kthSmallest(TreeNode root, int k) {
        inorderTreverse(root, k);
        return result;
    }
    public void inorderTreverse(TreeNode root, int k){
        if(root==null) return;
        System.out.println(result);
        inorderTreverse(root.left, k);
        count++;
        if(count==k) {
            result = root.val;
            return;
        }
        inorderTreverse(root.right, k);
    }
}

98. Validate Binary Search Tree

思路：
利用BST的第一条性质解题：每递归一个节点，还要递归该节点的所有子节点。时间复杂度O(n^2)。
利用第二条性质解题：中序遍历，只用递归一次，时间复杂度变为O(n)。

class Solution {
    private TreeNode pre;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        pre = null;
        return inOrder(root);
    }
    
    public boolean inOrder(TreeNode root){
        if(root==null) return true;
        if(!inOrder(root.left)) return false;
        if(pre!=null && root.val<=pre.val) return false;
        pre=root;
        return inOrder(root.right);
    }
}

参考： http://zxi.mytechroad.com/blog/tree/leetcode-98-validate-binary-search-tree/