给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。节点的右子树中的值要严格大于该节点的值。左右子树也必须是二叉查找树。一个节点的树也是二叉查找树。 样例一个例子：
2 / \ 1 4 / \ 3 5上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.
思路：观察二叉查找树，可以发现二叉查找树的一个特点，那就是二叉查找树中序遍历可以得到一个递增的序列，只需中序遍历二叉树，判断其序列是否递增即可。中序遍历的结果就是排序二叉树的输出，可以用中序遍历判定二叉树是否为二叉查找树。
红黑树、平衡搜索二叉树（AVL树）等，其实都是搜索二叉树的不同实现。
/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /* * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ bool isValidBST(TreeNode * root) { int lastvalue=0; //vector<int> tmp; //if(root==NULL) return tmp; stack<TreeNode*> s; TreeNode* cur=root; while(!s.empty()||cur!=NULL){ if(cur!=NULL){ //遍历左子树 s.push(cur); //把遍历的结点全部压栈 cur=cur->left; }else{ cur=s.top(); //tmp.push_back(cur->val); s.pop(); if(lastvalue==0||lastvalue<cur->val){ //如果是第一次弹出或lastvalue小于当前结点值 lastvalue = cur->val; }else if(lastvalue >= cur->val){ return false;//如果lastvalue大于当前结点值，返回false } cur=cur->right;//指向右子节点，下次循环时会中序遍历右子树 } } return true; } };
