开发者社区开发与运维文章正文

LeetCode（剑指 Offer）- 33. 二叉搜索树的后序遍历序列

2022-06-09 99

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode（剑指 Offer）- 33. 二叉搜索树的后序遍历序列

题目链接：点击打开链接

题目大意：略

解题思路

相关企业

微软（Microsoft）
Facebook
字节跳动

AC 代码

Java

classSolution {
publicbooleanverifyPostorder(int[] postorder) {
returnrecur(postorder, 0, postorder.length-1);
    }
booleanrecur(int[] postorder, inti, intj) {
if(i>=j) returntrue;
intp=i;
while(postorder[p] <postorder[j]) p++;
intm=p;
while(postorder[p] >postorder[j]) p++;
returnp==j&&recur(postorder, i, m-1) &&recur(postorder, m, j-1);
    }
}

C++

classSolution {
public:
boolverifyPostorder(vector<int>&postorder) {
returnrecur(postorder, 0, postorder.size() -1);
    }
private:
boolrecur(vector<int>&postorder, inti, intj) {
if(i>=j) returntrue;
intp=i;
while(postorder[p] <postorder[j]) p++;
intm=p;
while(postorder[p] >postorder[j]) p++;
returnp==j&&recur(postorder, i, m-1) &&recur(postorder, m, j-1);
    }
};