题目要求

given a binary tree, determine if it is a valid binary search tree (BST).Assume a BST is defined as follows:The left subtree of a node contains only nodes with keys less than the node's key.The right subtree of a node contains only nodes with keys greater than the node's key.Both the left and right subtrees must also be binary search trees.Example 1:    2   / \  1   3Binary tree [2,1,3], return true.Example 2:    1   / \  2   3Binary tree [1,2,3], return false.

判断一个树是否是二叉查找树。二叉查找树即满足当前节点左子树的值均小于当前节点的值，右子树的值均大于当前节点的值。

思路一：stack dfs

可以看到，对二叉查找树的中序遍历结果应当是一个递增的数组。这里我们用堆栈的方式实现中序遍历。

public boolean isValidBST(TreeNode root) {        long currentVal = Long.MIN_VALUE;        LinkedList
    
      stack = new LinkedList
     
      ();        while(root!=null || !stack.isEmpty()){            while(root!=null){                stack.push(root);                root = root.left;            }            root = stack.pop();            if(root.val<=currentVal) return false;            currentVal = root.val;            root = root.right;        }        return true;    }
     
    

思路二：递归

我们可以发现，如果已知当前节点的值val以及取值的上下限upper，lower，那么左子节点的取值范围就是(lower, val),右子节点的取值范围就是(val, upper)。由此出发递归判断，时间复杂度为O(n)因为每个节点只需要遍历一次。

public boolean isValidBST2(TreeNode root){        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);    }        public boolean isValid(TreeNode treeNode, long lowerBound, long upperBound){        if(treeNode==null) return true;        if(treeNode.val>=upperBound || treeNode.val<=lowerBound) return false;        return isValid(treeNode.left, lowerBound,treeNode.val) && isValid(treeNode.right, treeNode.val, upperBound);    }