leetcode98.Validate Binary Search Tree

发表于 更新于 分类于 ，

题目要求

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)因为每个节点只需要遍历一次。

1
2
3
4
5
6
7
8
9
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);
}