[leetcode][***] 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.

C++ wont initialize automatically for you!!!

Idea:

1. Inorder traversal and see if it is in the increasing order.

First Code(Run Time Error at first)：The problem is that I should initialize the pre pointer to NULL!

bool isValidBST(TreeNode *root) {
        if(!root) return true;
        stack<TreeNode*> s;
        TreeNode* temp = root;
        TreeNode* pre = NULL;
        TreeNode* cur;
        while(temp){
            s.push(temp);
            temp = temp->left;
        }
        while(!s.empty()){
            cur = s.top();
            if(pre)
                if(pre->val >= cur->val) return false;
            pre = cur;
            s.pop();
            if(cur->right){
                cur = cur->right;
                while(cur){
                    s.push(cur);
                    cur = cur->left;
                }
            }
        }
        return true;
    }