Validate Binary Search Tree

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.

http://www.lintcode.com/en/problem/validate-binary-search-tree/

Discussion

递归不难。注意判断根节点为INT_MIN, INT_MAX的情况。 或者中序遍历，看得到的结果是不是升序的。

Solution

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code here
        if(root == NULL) return true;
        if(root->val == INT_MAX) {
            return (root->right == NULL && isValidBST(root->left, INT_MIN, INT_MAX));
        } else if (root->val == INT_MIN) {
            return (root->left == NULL && isValidBST(root->right, INT_MIN, INT_MAX));
        }
        return isValidBST(root, INT_MIN, INT_MAX);
    }
private:
    bool isValidBST(TreeNode *root, int left, int right) {
        if (root == NULL) 
            return true;
        return (root->val > left && root->val < right)
                && isValidBST(root->left, left, root->val)
                && isValidBST(root->right, root->val, right);
    }
};

O(n) runtime, O(h) stack space

中序遍历的方法。

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // write your code here
        if(root == NULL) return true;
        vector<int> inorder = inorderTraversal(root);
        for(int i=0; i<inorder.size()-1; i++) {
            if(inorder[i+1] <= inorder[i]) {
                return false;
            }
        }
        return true;
    }
private:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == NULL) return result;
        TreeNode *cur = root;
        stack<TreeNode*> stk;
        while(cur) {
            stk.push(cur);
            cur = cur->left;
        }
        while(stk.empty() == false) {
            cur = stk.top();
            stk.pop();
            result.push_back(cur->val);
            cur = cur->right;
            while(cur) {
                stk.push(cur);
                cur = cur->left;
            }
        }
        return result;
    }
};

Follow up. How about don't save the inorder traversal result to save sapce? 仅仅初始化last_num为INT_MIN是不行的，因为第一个节点有可能就是最小值，所以需要判断正在输出的当前结点是否是inorder的第一个节点。

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
        // inorder traversal should be in a asending order
        TreeNode *cur = root;
        if(root == NULL) return true;
        int last_num  = INT_MIN;
        bool is_first = false;
        while(cur != NULL) {
            if(cur->left == NULL) {
                if(cur->val <= last_num && is_first == true) {
                    return false;
                }
                last_num = cur->val;
                if(is_first == false) {//the current node is the first node
                    is_first = true;
                }
                cur = cur->right;
            } else {
                TreeNode *tmp = cur->left;
                while(tmp->right != NULL && tmp->right != cur) {
                    tmp = tmp->right;
                }
                if(tmp->right == NULL) {
                    tmp->right = cur;
                    cur = cur->left;
                } else { //tmp->right == cur
                    tmp->right = NULL;
                    if(cur->val <= last_num && is_first == true) {
                        return false;
                    }
                    last_num = cur->val;
                    if(is_first == false) {
                        is_first = true;
                    }
                    cur = cur->right;
                }
            }
        }
        return true;
    }
};