Leetcode(98) Validate Binary Search Tree

发表于 | 分类于

Description

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:

1
2
3
4
5
Input:
    2
   / \
  1   3
Output: true

Example 2:

1
2
3
4
5
6
7
8
    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.

解法

这题最开始我想得简单了，直接递归解，比较当前点与左右节点是否符合，然后递归左右节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if ((root.left == null || root.left.val < root.val)&&(root.right == null || root.right.val > root.val)){
            return(isValidBST(root.left)&&isValidBST(root.right));
        }
        else{
            return false;
        }
    }
}

显然，这种做法是错误的，考虑如下情况：

1
2
3
4
5
  10
 / \
5   15
   / \
  6   20

它并不是一棵合法的二叉搜索树，上面的算法会误判。

所以，采用两个变量记录当前节点可能的最大最小值，在每次判断时与这两个值比较即可。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        return helper(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }

    boolean helper(TreeNode root, long max, long min) {
        if (root == null) {
            return true;
        }
        if (root.val < max && root.val > min) {
            return helper(root.left, root.val, min) && helper(root.right, max, root.val);
        } else {
            return false;
        }
    }
}