一、题目说明
题目98. Validate Binary Search Tree,给一个二叉树,判断是否是二叉搜索树。题目难度是Medium!
二、我的解答
这个题目,学过数据结构,会二叉树的中序遍历,不是很难。代码如下:
class Solution{
public:
//中序遍历
bool isValidBST(TreeNode* root){
stack<TreeNode*> st;
TreeNode* p = root,*pre = NULL;
if(p != NULL){
while(p!=NULL){
st.push(p);
p = p->left;
}
while(! st.empty()){
p = st.top();
st.pop();
if(pre!=NULL && pre->val>=p->val){
return false;
}
pre = p;
p = p->right;
while(p !=NULL){
st.push(p);
p = p->left;
}
}
}
return true;
}
};
性能如下:
Runtime: 16 ms, faster than 65.34% of C++ online submissions for Validate Binary Search Tree.
Memory Usage: 20.6 MB, less than 91.67% of C++ online submissions for Validate Binary Search Tree.
三、优化措施
上面是非递归算法,递归更简单,就不写了。