• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

LeetCode验证二叉查找树的两个不同问题


Recommended Posts

一、leetcode 98. 验证二叉搜索树

通过辅助功能增加参数来判断。

虽然节点值在INT范围内,但要求其有序遍历序列严格单调递增,所以等于是不可接受的,需要用LONG_MIN\LONG_MAX初始化最大最小值。

使用ll=long long

类别解决方案{

受保护的:

bool isBST(TreeNode* root,ll leftMin,ll rightMax){

如果(!root)返回true

if(root-val=left min | | root-val=right max){

返回false

}

return isBST(root-left,leftMin,root-val) isBST(root-right,root-val,right max);

}

公共:

bool isValidBST(TreeNode* root) {

如果(!root)返回true

return isBST(root,LONG_MIN,LONG _ MAX);

}

};

二、leetcode 255. 验证前序遍历序列二叉搜索树

验证前序遍历序列是否满足二叉查找树的要求。

因为前导遍历的顺序是:根左右;

所以遍历左子树时是递减的,可以用单调队列来维持。

遍历序列元素,

如果当前元素小于新弹出的元素,它一定不是二叉查找树。

如果堆栈不为空,且当前元素val大于顶层元素,则表示开始右子树,然后弹出顶层元素并更新为[Latest Top Element pre]直到小于顶层元素。

当前元素被堆叠。

如果所有的元素都能被遍历,那么它就是一个二叉查找树。

类别解决方案{

公共:

bool验证前序(矢量前序){

int pre=INT _ MIN

stackint单栈;

for(int I=0;I preorder . size();i ){

int curVal=preorder

if(曲线前){

返回false

}

而(!mono stack . empty()mono stack . top()curVal){

pre=mono stack . top();

mono stack . pop();

}

mono stack . push(curVal);

}

返回true

}

};

//5 2 1 3 6

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now