LeetCode Validate BST

解法一（中序遍历存储prev指针 递归）：

bool isValidBST(TreeNode* root) {
        TreeNode* prev = NULL;
        return helper(root, prev);
    }
    bool helper(TreeNode* root, TreeNode*& prev) {
        if(root == NULL) return true;
        if(!helper(root -> left, prev)) return false;
        if(prev && root -> val <= prev -> val) return false;
        prev = root;
        return helper(root -> right, prev);
    }

注：不要引用传int参数，int无法判断是不是中序遍历序列的第一个值，而指针可以根据是不是NULL判断。

解法二（中序遍历存储prev指针 迭代）：

bool isValidBST(TreeNode* root) {
        if(root == NULL) return true;
        TreeNode* cur = root, *prev = NULL;
        stack<TreeNode*> st;
        while(!st.empty() || cur) {
            if(cur){
                st.push(cur);
                cur = cur -> left;
            }
            else{
                TreeNode* tmp = st.top();
                st.pop();
                if(prev && prev -> val >= tmp -> val) return false;
                prev = tmp;
                cur = tmp -> right;
            }
        }
        return true;
    }

注：使用此方法还可以轻松求解出类似于第k大元素的问题。