面试题 04.05

Implement a function to check if a binary tree is a binary search tree.

Example 1:

Input: 2 / 1 3 Output: true Example 2:

Input: 5 / 1 4 / 3 6 Output: false Explanation: Input: [5,1,4,null,null,3,6]. the value of root node is 5, but its right child has value 4.

Solutions

1. inorder traversal

2. The sequence of inorder traversal are in strictly ascending order.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    long prev = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        if (!isValidBST(root->left)) return false;
        if (root->val <= prev) return false;
        prev = root->val;
        if (!isValidBST(root->right)) return false;
        return true;
    }
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long prev = LONG_MIN;
        stack<TreeNode *> s;

        while (root || s.size()) {
            while (root) {
                s.push(root);
                root = root->left;
            }
            root = s.top(); s.pop();
            if (root->val <= prev)
                return false;
            prev = root->val;
            root = root->right;
        }

        return true;
    }
};

1. preorder traversal

2. Recursively update and check if the current nodes's value is within the range of lower_bound and upper_bound defined by ascendant nodes.

class Solution {
public:
    bool check(TreeNode * root, long min, long max) {
        if (!root) return true;
        int cur = root->val;
        if (cur <= min || cur >= max)
            return false;
        return check(root->left, min, cur) 
            && check(root->right, cur, max);
    }
    bool isValidBST(TreeNode* root) {
        return check(root, LONG_MIN, LONG_MAX);
    }
};