95. Validate Binary Search Tree

9/15/2019
三种方法：
方法1：iteration，使用inorder iteration模板。时间复杂度O(n)，空间复杂度O(height), genrally O(logN).
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
bool isValidBST(TreeNode * root) {
// write your code here
stack<TreeNode *>stk;
TreeNode *pre = NULL;
TreeNode *p = root;

while(!stk.empty() || p != NULL){
     while(p != NULL){
          stk.push(p);
          p = p->left;
      }
       TreeNode *tmp = stk.top();
       stk.pop();

        if(pre != NULL){
            if(pre->val >= tmp->val){
                return false; 
            }
        }
        pre = tmp; 
        
        p = tmp->right; 
    }
    return true; 
}

};
方法二：recursion，需要另外一个helper函数辅助。和iteration的思路一致，用recursion方式（占用stack内存）替代方法一stack（占用heap内存）。一般recursion都可以对应一个带有stack的iteration方法。时间复杂度O(N), 如果只考虑heap内存，空间复杂度O(1)。一般函数调用使用的stack内存都是自动释放的，空间复杂度一般只考虑heap。可以先和面试官clarify。
bool isValidBST(TreeNode * root) {
// write your code here
TreeNode *pre = NULL;
return helper(root, pre);
}
bool helper(TreeNode *root, TreeNode *&pre){
if(root == NULL){
return true;
}
bool left = helper(root->left, pre);
if(!left){
return false;
}
if(pre){
if(pre->val >= root->val){
return false;
}
}
pre = root;
bool right = helper(root->right, pre);
return left && right;
}

方法三：
recursion，不需要辅助函数。直接用本身函数recursion。时间复杂度O（N），空间复杂度O（1）。

bool isValidBST(TreeNode * root) {
// write your code here
if(root == NULL){
return true;
}
if(root->left == NULL && root->right == NULL){
return true;
}
if(root->left != NULL){
if(root->val <= root->left->val){
return false;
}
TreeNode *tmp = root->left;
while(tmp->right != NULL){
tmp = tmp->right;
}
if(root->val <= tmp->val){
return false;
}
}
if(root->right != NULL){
if(root->val >= root->right->val){
return false;
}
TreeNode *tmp = root->right;
while(tmp->left != NULL){
tmp = tmp->left;
}
if(root->val >= tmp->val){
return false;
}
}
return isValidBST(root->left) && isValidBST(root->right);