水中的鱼: [LeetCode] Validate Binary Search Tree 解题报告

Given a binary tree, determine if it is a valid binary search tree (BST).

对于每一个子树，限制它的最大，最小值，如果超过则返回false。
对于根节点，最大最小都不限制；
每一层节点，左子树限制最大值小于根，右子树最小值大于根；
但是比较有趣的是，在递归的过程中还得不断带入祖父节点的值。

或者，中序遍历该树，然后扫描一遍看是否递增。
bool isValidBST(TreeNode *root) {
    return IsValidBST(root, INT_MIN, INT_MAX);
}
bool IsValidBST(TreeNode* node, int MIN, int MAX)  
{
    if(node == NULL)
          return true;
    if(node->val > MIN  
              && node->val < MAX
              && IsValidBST(node->left,MIN,node->val)
              && IsValidBST(node->right,node->val,MAX))
         return true;
    else  
         return false;
}
From: http://yucoding.blogspot.com/2013/02/leetcode-question-122-validate-binary.html

    void inOrder(TreeNode* root, int &pre, bool &res){

        if (!root || !res ){return;}

        inOrder(root->left,pre,res);

        if (pre>=root->val){

            res = false; return;

        }else{

            pre = root->val;

        }

        inOrder(root->right,pre,res);

    }

 

    bool isValidBST(TreeNode *root) {

        if (!root){return true;}

        int pre = INT_MIN;

        bool res=true;

        inOrder(root,pre,res);

        return res;

    }

Read full article from 水中的鱼: [LeetCode] Validate Binary Search Tree 解题报告