Validate Binary Search Tree

LeetCode #98

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.

Example:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Idea:

recursion的时候携带一个指向Node的指针（应该是指向指针的指针，因为Node用指针表示），让该指针指向pre visted的Node，然后跟现Node对比。

需要处理好各种return情况，同时，call这个function的时候需要给Node指针的地址而不能给Null.

指针回顾：

int a=1;
int b;
int *ptr=&a;
*ptr = 2; //Now a==2
ptr=&b; //Now ptr point to b

Code:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode *pre=NULL;

        //注意！pre指向前一个visited node，所以在传递过程中必须能够带回修改的值。
        //parameter需要时TreeNode **, 但是argument不能是null, 
        //因为*pre_ptr要是一个TreeNode的指针，如果是null不能dereference

        return checkValidBST(root, &pre);
    }

    bool checkValidBST(TreeNode *root, TreeNode **pre_ptr){
        if(root==NULL) return true;

        if(!checkValidBST(root->left, pre_ptr)) 
            return false;

        if(*pre_ptr==NULL){ 
            *pre_ptr=root;
        }
        else{
            if((*pre_ptr)->val >= root->val)
                return false;

            *pre_ptr=root;
        }

        if(!checkValidBST(root->right, pre_ptr)) 
            return false;

        return true;
    }

};