题目：
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.
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (!root) return true;
stack<TreeNode *> sta;
vector<int> traversal;
TreeNode *p = root;
while ( !sta.empty() || p )
{
if (p){
sta.push(p);
p = p->left;
}
else{
p = sta.top();
sta.pop();
if ( !traversal.empty() && traversal[traversal.size()-]>=p->val ) return false;
traversal.push_back(p->val);
p = p->right;
}
}
return true;
}
};
tips：
中序遍历BST；并保留每次访问的元素；如果中序遍历的前一个元素不小于后一个元素，则返回false；全部遍历过后无问题，则返回true。
题目中有一个test case是：[-2147483648]，即INT_MIN。由于有这个非常极端的case存在，之前那种设一个pre = INT_MIN的办法就行不通了，暂时老老实实用一个vector来代替。
==========================================
一开始刷这道题总想用递归，后来看的之前的代码，BST这种判断有效的，用中序遍历可能更好一些。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> sta;
TreeNode* curr = root;
vector<int> vals;
while ( !sta.empty() || curr )
{
if ( curr )
{
sta.push(curr);
curr = curr->left;
}
else
{
curr = sta.top();
vals.push_back(curr->val);
sta.pop();
if ( vals.size()> && vals[vals.size()-]<=vals[vals.size()-] ) return false;
curr = curr->right;
}
}
return true;
}
};