验证二叉搜索树

验证二叉搜索树

题目:
给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
2
/
1 3
输出: true
示例 2:

输入:
5
/
1 4
/
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。

解题思路：有两种思路，第一种是根据二叉树性质对树进行中序遍历然后判断是否满足性质
另外一种是用递归进行判断

第一种：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<Integer> list = new ArrayList();
    public boolean isValidBST(TreeNode root) {
        postOrder(root);
        for(int i = 1; i < list.size(); i++) {
            if(list.get(i - 1) >= list.get(i))
                return false;
        }
        return true;
    }
    
    private void postOrder(TreeNode node) {
        if(node == null)
            return ;
        postOrder(node.left);
        list.add(node.val);
        postOrder(node.right);
    }
}

第二种

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, null, null);
    }
    
    /**
    维护了lower和upper，当遍历左子树时upper为当前根节点的值，遍历右子树时则将lower设为当前节点值
   	需要判断当前节点值是否在lower和upper之间，如果不在则说明该树不是二叉搜索树
    **/
    private boolean dfs(TreeNode node, Integer lower, Integer upper) {
        if(node == null)
            return true;
        
        int val = node.val;
        if(lower != null && val <= lower) {
            return false;
        }
        
        if(upper != null && val >= upper) {
            return false;
        }
        
        return dfs(node.left, lower, node.val) && dfs(node.right, node.val, upper);
    }
}