98. Validate Binary Search Tree

Leetcode Tree Depth-first Search

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:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

分析¶

这道题目题意非常清楚：确认二叉树是否为二叉搜索树。所以最笨的方法就是使用题目定义的三种条件去一一确认。使用前序遍历获得子树的节点，这里直接照搬144. Binary Tree Preorder Traversal的代码过来。时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n^2)$ 。

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    // 确认左子树节点都小于该节点
    for(int i: preorderTraversal(root.left))
        if (i >= root.val) return false;
    // 确认右子树节点都大于该节点
    for(int i: preorderTraversal(root.right))
        if (i <= root.val) return false; 
    // 确认左子树和右子树也是二叉搜索树
    return isValidBST(root.left) && isValidBST(root.right);    
}


private List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();
    preorderTraversalHelper(root, list); 
    return list;
}

private void preorderTraversalHelper(TreeNode root, List<Integer> list) {
    if (root == null) return;
    list.add(root.val);
    preorderTraversalHelper(root.left, list);
    preorderTraversalHelper(root.right, list);
}

优化一下，在遍历的时候进行判断。由于右子树和左子树的判断条件不同，所以写了两个函数preorderTraversalLeft、preorderTraversalRight分别进行遍历并判断。返回的结果是，是否符合给定的条件。时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(1)$ 。

public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (!preorderTraversalLeft(root.left, root.val)) return false;
    if (!preorderTraversalRight(root.right, root.val)) return false;

    return isValidBST(root.left) && isValidBST(root.right);    
}


private boolean preorderTraversalLeft(TreeNode root, int comparison) {
    if (root == null) return true;
    if (root.val >= comparison) return false;
    return preorderTraversalLeft(root.left, comparison) &&
        preorderTraversalLeft(root.right, comparison);

}

private boolean preorderTraversalRight(TreeNode root, int comparison) {
    if (root == null) return true;
    if (root.val <= comparison) return false;
    return preorderTraversalRight(root.left, comparison) &&
        preorderTraversalRight(root.right, comparison);
}

其实这道题目有个trick，因为二叉搜索树的中序遍历有个特点，它是个递增序列。所以只需要中序遍历二叉搜索树一次，然后看看中序遍历是否是递增序列即可。中序遍历的方法可以参照94. Binary Tree Inorder Traversal，这里直接照搬过来了。时间复杂度为 $O(n)$ ，空间复杂度为 $O(2n)$ 。空间复杂度为 $O(2n)$ 的原因是一个List保存遍历结果，一个Stack保存将要遍历的节点。

public boolean isValidBST(TreeNode root) {
    List<Integer> list = inOrderTraversal(root);
    int i = 0;
    while (++i < list.size()) {
        if (list.get(i) <= list.get(i - 1)) return false;
    }
    return true;

}

private List<Integer> inOrderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        // reach left 
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }
    return list;
}

同样的，写完以后肯定会有疑问，是否可以边遍历边判断呢？答案当然是肯定的。既然中序遍历是一个递增序列，那么只要保存前面一个遍历节点prev，然后比较现在的节点cur是否大于前面节点prev就行了。用不到保存遍历结果。时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

public boolean isValidBST(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    int prevVal = Integer.MIN_VALUE;
    int num = 0; // the lenght of the in-order traversal
    while (cur != null || !stack.isEmpty()) {
        // reach left 
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (num != 0 && cur.val <= prevVal) return false;
        num++;
        prevVal = cur.val;
        cur = cur.right;
    }
    return true;
}

但是还是可以再快一点。可以进一步降低空间复杂度为 $O(1)$ 。因为中序遍历有多种方法，最快的一种是带有帮助函数的递归。所以可以应用该种递归，然后在递归时进行判断。这种方法击败了100%，运行时间只有0ms。

private int prev;   // 前一个节点的值
private int num = 0;   // 遍历的节点个数
public boolean isValidBST(TreeNode root) {
    prev = Integer.MIN_VALUE;
    num = 0;
    return inorderTraversalHelper(root);
}

private boolean inorderTraversalHelper(TreeNode root) {
    if (root == null) return true;
    if (!inorderTraversalHelper(root.left)) return false;
    if (num++ != 0 && root.val <= prev) return false;
    prev = root.val;
    if (!inorderTraversalHelper(root.right)) return false;
    return true;
}