> 二叉搜索树验证。对于binary search tree的概念都懂，但是如何通过程序验证还是第一次，问题百出。 - Approach 1 ： recursive - Approach 2 ： in-order traversal

in-order.cpp

//Runtime: 20 ms, faster than 99.86% 
//Memory Usage: 20.8 MB, less than 21.53% 

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = NULL;
        return validate(root,prev);
    }
    bool validate(TreeNode* node,TreeNode* &prev){
        if(node == NULL) return true;
        if(!validate(node->left,prev)) return false;
        if(prev != NULL && prev->val >= node->val) return false;
        prev = node;
        return validate(node->right,prev);
    }
};

recursive.cpp

//Runtime: 20 ms, faster than 99.86%
//Memory Usage: 20.7 MB, less than 37.44%

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root,NULL,NULL);
    }
    bool isValidBST(TreeNode* root,TreeNode* minNode,TreeNode* maxNode){
        if(!root) return true;
        if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
            return false;
        return isValidBST(root->left,minNode,root) && isValidBST(root->right,root,maxNode);
    }
};