leetcode98 Validate Binary Search Tree

一开始想到使用中序遍历解决

• 即中序遍历必须是升序
• 但是需要额外的变量记录先前遍历到的值（在整数的范围内题目数据范围限制不可以取一个特殊的值）

可以考虑换种思路。
采用先序遍历的想法：

• 遍历到一个结点，首先查看当前结点是否在给定范围内
  • 如果在，则继续
  • 如果不在，直接返回假
• 置这个给定范围最小值为这个遍历到的结点，最大值不变，遍历右子树
• 置这个给定范围最小值不变，最大值为遍历到的结点，遍历左子树
  AC代码（借鉴别人的）

   class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}