Description

Title

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

Input: [2,1,3]

Output: true

Example 2:

    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

中序遍历时，val应当有序。

 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

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }

        long first = LONG_MIN;
        return visit(root, first);
    }

private:
    bool visit(TreeNode* root, long &last) {
        if (root->left && !visit(root->left, last)) {
            return false;
        }

        if (root->val <= last) {
            return false;
        }
        last = root->val;

        if (root->right && !visit(root->right, last)) {
            return false;
        }

        return true;
    }
};