NO CODING NO LIFE: Lintcode: 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.

Have you met this question in a real interview?

Yes

Example

An example:

The above binary tree is serialized as {2,1,3,#,#,4,#,#,5} (in level order).

Tags Expand

Divide and Conquer Recursion Binary Search Tree Binary Tree

Two types:
1. get the max and min range of each node, traverse inorder recursively
2. traverse inorder recursively or iteratively, compare current node value and the previous traversed node value

O(n*n) naive solution:

Note: when compare left/right value with current node value, don't forget add equation ==> false

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
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;
        int left = root->val;
        int right = root->val;
        if(root->left) {
            left = getMax(root->left);
            if (left >= root->val || !isValidBST(root->left)) return false;
        }
        if(root->right) {
            right = getMin(root->right);
            if (right <= root->val || !isValidBST(root->right)) return false;
        }
        return true;
    }
    
    int getMax(TreeNode *node){
        int res = node->val;
        int left, right;
        left = right =res;
        if(node->left) left= getMax(node->left);
        if(node->right) right = getMax(node->right);
        int big = max(left, right);
        if(big > res) return big;
        return res;
    }
    
    int getMin(TreeNode *node){
        int res = node->val;
        int left, right;
        left = right =res;
        if(node->left) left= getMin(node->left);
        if(node->right) right = getMin(node->right);
        int small = min(left, right);
        if(small < res) return small;
        return res;
    }
};

http://scyforce.gitbooks.io/leetcode/content/validate_binary_search_tree.html
Recursive:
preorder

This is the most popular version

Remember to make sure the range of value in node, here to pass the test, we use long type

When traverse the BST preorder, we just need root value to make sure the upper limit and bottom limit for left and right subtree. So we can transmit these two limits to next node.

Time: O(n)
Space: O(L)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
   
    bool inorder(TreeNode* node, long max, long min){
        if(!node) return true;
        if(node->val >= max || node->val <= min) return false;
        return inorder(node->left, node->val, min) && inorder(node->right, max, node->val);
    }
    bool isValidBST(TreeNode *root) {
        if(!root) return true;
        return inorder(root, LONG_MAX, LONG_MIN);
    }

};

Inorder:
Global variable is needed, not recommended.
But iteritive solution avoid this problem well.
http://www.lifeincode.net/programming/leetcode-validate-binary-search-tree-java/

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    bool isValidBST(TreeNode *root) {
       return inorder(root);
    }
    TreeNode* prev = NULL;
    bool inorder(TreeNode* root){
        if(root == NULL) return true;
        if(!inorder(root->left)) return false;
        if(prev != NULL){
            if(root->val <= prev->val) return false;
        }
        prev = root;
        if(!inorder(root->right)) return false;
        return true;
    }
};

Lintcode second:

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

Iterative:
Traverse inorder with stack, just make sure the current value is bigger than previous value
http://pengweilan.gitbooks.io/leetcode/content/Tree/validate_binary_search_tree.html
Iterative inorder BST:
http://articles.leetcode.com/2010/04/binary-search-tree-in-order-traversal.html

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
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 her
        stack<TreeNode*> s;
        TreeNode* cur = root;
        TreeNode* prev = NULL;
        while(!s.empty() || cur != NULL){
            if(cur != NULL){
                s.push(cur);
                cur = cur->left;
            }else{
                cur = s.top();
                s.pop();
                if(prev && prev->val >= cur->val) return false;
                prev = cur;
                cur = cur->right;
            }
        }
        return true;
    }
};

NO CODING NO LIFE

2015年9月10日星期四

Lintcode: Validate Binary Search Tree

没有评论:

发表评论