Task

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

  • Example 1:
1
2
3
4
5
6

    2
   / \
  1   3

Input: [2,1,3]
Output: true
  • Example 2:
1
2
3
4
5
6
7
8
9

    5
   / \
  1   4
     / \
    3   6

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

Solution

  • 对树上的每个节点都定义一个取值范围，若存在某节点在自己的取值范围之外，则不是BST
  • 判断时递归遍历BST的过程即是不断确定每个节点应该的取值范围的过程：
    • 根节点的范围是负无穷到正无穷
    • 对于每个节点：
      • 其左子节点不能大于它，故左子节点取值范围的上界被它界定
      • 其右子节点不能小于它，故右子节点取值范围的下界被它界定
      • 若该节点为空（即其父节点的这个子节点指针为NULL）则到达递归终点，返回true
      • 若该节点在取值范围之外，则返回false
    • 对所有节点的判断结果取&&，即只要遇到一个节点不满足条件，就直接false
  • 实现时用nullptr表示无穷大的，正负无穷大皆可，比较时若一侧为nullptr则认为这一侧自动满足取值范围
  • 最好不要用某个确定的值作为正负无穷，因为不知道给的数的取值范围
  • 时间复杂度：最坏情形要遍历每个元素，故O(n)
  • 空间复杂度：最好情形是完全二叉树，最坏情形是链表，即递归深度在O(logn)-O(n)之间
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Runtime: 8 ms, faster than 99.49% of C++ online submissions for Validate Binary Search Tree.
// Memory Usage: 21.7 MB, less than 5.21% of C++ online submissions for Validate Binary Search Tree.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        //用无穷大来初始化根节点范围
        return isValidBST(root,nullptr,nullptr);
    }
private:
    bool isValidBST(TreeNode *root,int *inf,int *sup){
        //该节点不存在则true
        if(!root) return true;
        //该节点超出取值范围则为false
        if((inf && root->val<=*inf) || (sup && root->val>=*sup)) return false;
        //遍历树，只要发生false则返回false
        return isValidBST(root->left,inf,&(root->val)) && 
               isValidBST(root->right,&(root->val),sup);
    }
};