Validate Binary Search Tree

Description

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.
• A single node tree is a BST

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

Link

Lintcode_ladder

Method

1. keep
2. x

Example

1. 1

/**
 * 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
        return helper(root, NULL, NULL);
    }
private:
    bool helper(TreeNode* root, TreeNode* min, TreeNode* max){
        if (!root) {
            return true;
        }
        // bool left = true, right = true;
        if (min && root->val <= min->val) {
            return false;
        }
        if (max && root->val >= max->val) {
            return false;
        }
        return helper(root->left, min, root) && helper(root->right, root, max);
    }
};

Similar problems

x

Tags

x