NO23、二叉搜索树的后序遍历序列(好题,值得再看一遍)
23、二叉搜索树的后序遍历序列 好题,值得再看一遍
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
示例1
输入
[4,8,6,12,16,14,10]
返回值
true
1、递归写法,树主要的做法就是递归
bool VerifySquenceOfBST(vector<int> sequence) { if (sequence.empty()) return false; if (sequence.size() == 1) return true; return VerifySquenceOfBSTCore(sequence, 0, sequence.size()-1); } bool VerifySquenceOfBSTCore(vector<int>& sequence, int start, int end) { if (start >= end) return true; int low = start; while (low < end && sequence[low] < sequence[end]) ++low; for (int i = low; i < end; ++i) { if (sequence[i] <= sequence[end]) return false; } return VerifySquenceOfBSTCore(seq
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
带你刷完67道剑指offer 文章被收录于专栏
- 本专栏汇集了67道剑指offer的一些精妙解法,不少题有5-6种解法之多,有些题目二刷三刷的解法也不一样。 - 本专栏帮助我拿到6个互联网大厂offer,最终圆梦字节跳动公司。