题目

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

一个二叉搜索树有如下定义：

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

思路

错误的思路：递归一遍，判断每个节点是否大于其左孩子并小于其右孩子。这样是错误的，因为定义中说的是小于、大于子树的所有结点，而不只是直接孩子结点。这样判断不能保证正确。
正确的思路：由二叉搜索树的特点可知，其中序遍历序列一定是一个升序序列，反之中序为升序的二叉树也一定是二叉搜索树。所以求出其中序序列再判断是否为升序就行了。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private static List<Integer> list = new ArrayList<Integer>();
    public boolean isValidBST(TreeNode root) {
        if(!list.isEmpty())
            list.clear();
        dfs(root);
        boolean ans = true;
        int len = list.size();
        for(int i = 1; i < len; i++) {
            if(list.get(i) <= list.get(i-1)) {
                ans = false;
                break;
            }
        }
        return ans;
    }

    private void dfs(TreeNode root) {
        if(root == null) return;

        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}