刷题98. Validate Binary Search Tree

一、题目说明

题目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.

三、优化措施

上面是非递归算法,递归更简单,就不写了。

上一篇:mysql5.7初始化密码报错 ERROR 1820 (HY000)


下一篇:javascript:

元素