问题描述
解题报告
由于二叉搜索树中，树上任何一个节点，它的值比所有的左子树大，比所有的右子树小
遇到左子树时，全部入栈，遇到右子树时，将与其平级的左子树出栈【它具有大于平级左子树的性质】； 出现出栈的时候，新来的元素必定是大于已经出栈的元素。
代码实现
class Solution {
public:
bool verifyPreorder(vector
<int>& preorder
) {
if (!preorder
.size()) return true;
stack
<int> s
;
s
.push(preorder
[0]);
int temp
= -1e10;
for (int i
=1;i
<preorder
.size();i
++)
{
if (preorder
[i
] < temp
) return false;
while(!s
.empty() && preorder
[i
] > s
.top())
{
temp
=s
.top();
s
.pop();
}
s
.push(preorder
[i
]);
}
return true;
}
};
