题目要求
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 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.判断一个树是否是二叉查找树。二叉查找树即满足当前节点左子树的值均小于当前节点的值，右子树的值均大于当前节点的值。
思路一：stack dfs
可以看到，对二叉查找树的中序遍历结果应当是一个递增的数组。这里我们用堆栈的方式实现中序遍历。
public boolean isValidBST(TreeNode root) {
long currentVal = Long.MIN_VALUE;
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
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);
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
