LintCode - 验证二叉查找树（中等）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：入门

要求：

给定一个二叉树，判断它是否是合法的二叉查找树(BST)

一棵BST定义为：

节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。

样例:

一个例子：

  2
 / \
1   4
   / \
  3   5

上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

思路：

方法一： 根据定义递归验证
方法二： 二叉查找树中序遍历可以得到一个递增的序列

这里我们实现方法二:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();

        //遍历
        inOrder(root, list);

        //校验
        boolean flag = true;
        int cur = Integer.MIN_VALUE;
        if(list.size() > 0){
            cur = list.get(0);
            list.remove(0);
        }
        for(int i : list){
            if(i <= cur){
                flag = false;
                break;
            }else{
                cur = i;
            }
        }
        return flag;
    }
    
    /**
     * 二叉查找树中序遍历可以得到一个递增的序列
     * 
     **/
    private void inOrder(TreeNode node, List<Integer> list){
        if(node == null){
            return;
        }
        
        inOrder(node.left, list);
        list.add(node.val);
        inOrder(node.right, list);
        return;
    }
}