输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
class Solution {
public:
bool verifyPostorder(vector
<int>& postorder
) {
int n
= postorder
.size();
if(n
< 1)
return 1;
int m
= INT_MAX
;
stack
<int> root
;
root
.push(INT_MIN
);
for(int i
= n
- 1; i
>= 0; --i
) {
if(postorder
[i
] > m
)
return 0;
while(postorder
[i
] < root
.top()) {
m
= root
.top();
root
.pop();
}
root
.push(postorder
[i
]);
}
return 1;
}
};
这个代码巨简洁,说实话并没有怎么看懂
转载请注明原文地址:https://blackberry.8miu.com/read-26792.html