对一棵二叉树进行中序遍历可以得到一个递增序列，基于这个思想，我们可以写出递归和非递归的代码，它们都是基于二叉树的中序遍历。
递归版本：
//递归 /*中序遍历*/ int last = INT_MIN; //pre保存当前结点中序前趋的值 bool isValidBST(Tree& t){ if(t == NULL) return true; if(isValidBST(t->left)){ //检查左子树 if(last < t->val){ last = t->val; return isValidBST(t->right); //检查右子树 } } return false; //有任意一处不符合规则，返回false }非递归版本：
//非递归 /*中序非递归再加一个判断条件。*/ bool IsValidBST(Tree& t){ stack<TreeNode*> s; int pre = INT_MIN; //pre保存当前结点中序前趋的值 TreeNode* p = t; while(!s.empty() || p!=NULL){ while(p != NULL){ s.push(p); p = p->left; } p = s.top(); s.pop(); if(p->val <= pre) return false; pre = p->val; p = p->right; } return true; }完整代码：
#include<iostream> #include<stack> #include<algorithm> using namespace std; typedef struct node{ int val; struct node* left; struct node* right; }TreeNode,*Tree; //递归 /*中序遍历*/ int last = INT_MIN; //pre保存当前结点中序前趋的值 bool isValidBST(Tree& t){ if(t == NULL) return true; if(isValidBST(t->left)){ //检查左子树 if(last < t->val){ last = t->val; return isValidBST(t->right); //检查右子树 } } return false; //有任意一处不符合规则，返回false } //非递归 /*中序非递归再加一个判断条件。*/ bool IsValidBST(Tree& t){ stack<TreeNode*> s; int pre = INT_MIN; //pre保存当前结点中序前趋的值 TreeNode* p = t; while(!s.empty() || p!=NULL){ while(p != NULL){ s.push(p); p = p->left; } p = s.top(); s.pop(); if(p->val <= pre) return false; pre = p->val; p = p->right; } return true; } void CreateTree(Tree& t){ int x; cin>>x; if(x == 9) t = NULL; else{ t = new TreeNode; t->val = x; CreateTree(t->left); CreateTree(t->right); } } int main(){ Tree t; CreateTree(t); /* 4 2 1 9 9 3 9 9 6 5 9 9 9 */ cout<<"isValidBST:"<<endl; cout<<isValidBST(t); cout<<"IsValidBST:"<<endl; cout<<IsValidBST(t); }运行结果：
