剑指 Offer 33. 二叉搜索树的后序遍历序列
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回
true
,否则返回false
。假设输入的数组的任意两个数字都互不相同。
DFS
思路
采用分治算法,若该数组可以生成搜索树,则其左右子树也是搜索树。由于后序遍历顺序为【左右根】,故最后一个节点必然为根节点,且遍历数组到第一个>根节点的点必然为右子树中的最左的点,故可以得到左右子树对应的子数组。
对于二叉搜索树,满足【左<根<右】,故依据划分点判断是否满足上述条件,若满足则继续【划分】,若不满足则return false;
算法
recur(i,j)
:
i,j表示子树的范围
- 遍历
[i,j]
范围内的数组,找到第一个>postorder[j]
的位置,记该位置为m
- 判断
[m,j-1]内
的节点是否>postorder[j],若不满足,则return,若满足,则继续第三步 - recur(i,m-1) && recur(m,j-1);
边界条件:
- 若i>=j,显然可以构造搜索树,返回true;
实现
```cpp bool recur(vector& order,i,j){ if(i>=j) return true; int rootVal=order[j],m=i; while(order[m]<=rootVal) ++m; for(int k=m;k<j;k++){
} return recur(order,i,m-1) && recur(order,m,j-1); }if(order[m]<rootVal) return false;
<a name="7k4jf"></a>
## 复杂度分析
- 时间复杂度:![](https://cdn.nlark.com/yuque/__latex/8e9c5fee65a4f32abccd0e83ff203e39.svg#card=math&code=O%28N%5E2%29&height=20&width=43),最差的情况,每次recur减去一个节点,即递归占用O(N);每轮递归都需要遍历所有节点,占用O(N);
- 空间复杂度:![](https://cdn.nlark.com/yuque/__latex/33697ce7dfa48ba80980d298c8089378.svg#card=math&code=O%28N%29&height=26&width=51),最差情况下,树退化为链表,递归深度达到O(N)
<a name="jxlcG"></a>
## ❤❤❤单调栈
<a name="i7EcZ"></a>
### 思路
- **后序遍历倒序**: `[ 根节点 | 右子树 | 左子树 ]` 。类似 先序遍历的镜像 ,即先序遍历为 “根、左、右” 的顺序,而后序遍历的倒序为 “根、右、左” 顺序。
![](https://cdn.nlark.com/yuque/0/2020/png/2728415/1605166134849-38ce8ced-b873-436c-a87e-402add9ded08.png#align=left&display=inline&height=658&margin=%5Bobject%20Object%5D&originHeight=658&originWidth=876&size=0&status=done&style=none&width=876)
- 设后续遍历的倒序列表为[![](https://cdn.nlark.com/yuque/__latex/382c73b58c768674272dd0d16e091de3.svg#card=math&code=r_n%2Cr_%7Bn-1%7D%2C...%2Cr_1&height=12&width=96)],遍历此列表,设索引值i,若为二叉搜索树,则
- ![](https://cdn.nlark.com/yuque/__latex/66ac88f6617377693d3943fc49d5ee08.svg#card=math&code=r_i%3Er_%7Bi%2B1%7D%EF%BC%8C%E5%88%99r_i%E5%BF%85%E8%A6%81%E4%B8%BAr_%7Bi%2B1%7D%E7%9A%84%E5%8F%B3%E5%AD%90%E8%8A%82%E7%82%B9%E3%80%82%0A&height=21&width=247)
- ![](https://cdn.nlark.com/yuque/__latex/8b74716bcd08c05a03343a57556d5e8b.svg#card=math&code=r_i%3Cr_%7Bi%2B1%7D%EF%BC%8C%E5%88%99r_i%E5%BF%85%E7%84%B6%E6%9F%90root%E7%9A%84%E5%B7%A6%E5%AD%90%E8%8A%82%E7%82%B9%EF%BC%8C%E4%B8%94%E8%AF%A5root%E4%BD%8D%E4%B8%8E%5Br_%7Bi%2B1%7D%2C...%2Cr_n%5D%E4%B9%8B%E9%97%B4%E6%9F%90%E4%B8%AA%E6%9C%80%E6%8E%A5%E8%BF%91%E4%B8%94%EF%BC%9Er_i%E7%9A%84%E5%80%BC&height=21&width=578)
- 当遍历倒序后序时,若遭遇![](https://cdn.nlark.com/yuque/__latex/923f90d32bcd78331271a1d57a02c6d0.svg#card=math&code=r_i%3Cr_%7Bi%2B1%7D&height=13&width=57),则后续遍历的任意节点[![](https://cdn.nlark.com/yuque/__latex/0c5cdb051e1ce485d2408b80b6847479.svg#card=math&code=r_%7Bi-1%7D%2C...%2Cr_1&height=12&width=72)]![](https://cdn.nlark.com/yuque/__latex/85b92566aabdcea1390b4c8a236de528.svg#card=math&code=%E5%BF%85%E7%84%B6%E6%9C%89r_x%3Croot&height=21&width=102)。
> 节点![](https://cdn.nlark.com/yuque/__latex/5d665d9b1ed45c11d501a6d152e83a8a.svg#card=math&code=r_x&height=12&width=14)仅有两种情况:1.![](https://cdn.nlark.com/yuque/__latex/5d665d9b1ed45c11d501a6d152e83a8a.svg#card=math&code=r_x&height=12&width=14)为![](https://cdn.nlark.com/yuque/__latex/af2593b49488f8bc44396795792c2d79.svg#card=math&code=r_i%0A&height=12&width=12)的左右子树节点,2.当root为右子树节点时,![](https://cdn.nlark.com/yuque/__latex/5d665d9b1ed45c11d501a6d152e83a8a.svg#card=math&code=r_x&height=12&width=14)为root的父节点或更高层父节点的左子树各节点
- 遍历“后序遍历的倒序列表”会多次遇到递减节点![](https://cdn.nlark.com/yuque/__latex/af2593b49488f8bc44396795792c2d79.svg#card=math&code=r_i&height=12&width=12)![](https://cdn.nlark.com/yuque/__latex/33ee1b51796c3430c94430dd8d1e6833.svg#card=math&code=%EF%BC%8C%E8%8B%A5%E6%89%80%E6%9C%89%E9%80%92%E5%87%8F%E8%8A%82%E7%82%B9r_i%E5%AF%B9%E5%BA%94%E7%9A%84%E7%88%B6%E8%8A%82%E7%82%B9root%E9%83%BD%E6%BB%A1%E8%B6%B3%E4%BB%A5%E4%B8%8A%E6%9D%A1%E4%BB%B6%EF%BC%8C&height=21&width=345)则可判定为二叉搜索树
- 考虑以上特性,借助“**单调栈**”实现。
1. 借助一个单调栈存储递增的节点;
1. 每当遇到递减节点![](https://cdn.nlark.com/yuque/__latex/af2593b49488f8bc44396795792c2d79.svg#card=math&code=r_i&height=12&width=12),则通过栈来更新![](https://cdn.nlark.com/yuque/__latex/af2593b49488f8bc44396795792c2d79.svg#card=math&code=r_i&height=12&width=12)父节点root.
1. 每轮判断![](https://cdn.nlark.com/yuque/__latex/e4ea3ae02e94d0347b1f42eae5de49b6.svg#card=math&code=r_i%E5%92%8Croot%E5%85%B3%E7%B3%BB%0A&height=21&width=80):
1. ![](https://cdn.nlark.com/yuque/__latex/8794e9abca056687c83458b21d9035b4.svg#card=math&code=r_i%3Eroot%EF%BC%8C%E4%B8%8D%E6%BB%A1%E8%B6%B3%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E5%AE%9A%E4%B9%89%0A&height=21&width=211)
1. ![](https://cdn.nlark.com/yuque/__latex/66748d59bd932990a463be9cbcdd4731.svg#card=math&code=r_i%3Croot%EF%BC%8C%E6%BB%A1%E8%B6%B3%EF%BC%8C%E7%BB%A7%E7%BB%AD%E9%81%8D%E5%8E%86&height=21&width=169)
<a name="hmeVu"></a>
### 算法
1. **初始化**:单调栈stack,![](https://cdn.nlark.com/yuque/__latex/22c4df0ce3c5c0d8cb2a8a29609a032f.svg#card=math&code=root%3D%E6%AD%A3%E6%97%A0%E7%A9%B7%E5%A4%A7%EF%BC%88%E5%8F%AF%E5%B0%86%E6%A0%91%E5%8E%9F%E6%A0%B9%E8%8A%82%E7%82%B9%E7%9C%8B%E4%BD%9C%E8%AF%A5root%E7%9A%84%E5%B7%A6%E5%AD%90%E6%A0%91%EF%BC%89&height=21&width=352)
1. **倒序遍历**:记每个节点为![](https://cdn.nlark.com/yuque/__latex/af2593b49488f8bc44396795792c2d79.svg#card=math&code=r_i&height=12&width=12)
1. **判断:**![](https://cdn.nlark.com/yuque/__latex/fcf3bf606ced8d5b894a3f7ac040ef11.svg#card=math&code=r_i%3Eroot%EF%BC%8C%E8%AF%B4%E6%98%8E%E4%B8%8D%E6%BB%A1%E8%B6%B3%E4%BA%8C%E5%8F%89%E6%A0%91%E6%90%9C%E7%B4%A2%E5%AE%9A%E4%B9%89%EF%BC%8Cfalse%3B&height=21&width=292)
1. **更新父节点:**当栈不空时且![](https://cdn.nlark.com/yuque/__latex/080415e2fc0d9f07a0c83e7eb099fad4.svg#card=math&code=r_i%3Cstack.top%28%29&height=18&width=104),循环执行出栈,将出栈节点赋值给root。
1. **入栈:将![](https://cdn.nlark.com/yuque/__latex/af2593b49488f8bc44396795792c2d79.svg#card=math&code=r_i&height=12&width=12)入栈**
3. 若遍历完成,则返回true;
<a name="CvnWR"></a>
### 实现
```cpp
bool verifyPostorder(vector<int>& postorder) {
stack<int> mtStack;
int root=INT_MAX;
for(int i=postorder.size()-1;i>-1;i--){
if(postorder[i]>root) return false;
while(!mtStack.empty() && mtStack.top()>postorder[i]){
root=mtStack.top();
mtStack.pop();
}
mtStack.push(postorder[i]);
}
return true;
复杂度分析
- 时间复杂度:
- 空间复杂度:,最差的情况,全部都是递减,单调栈存储所有节点
题目标题难度划分
星级 | 题目难度 |
---|---|
☆ | 简单 |
☆☆ | 中等 |
☆☆☆ | 困难 |
算法掌握难度程度划分
星级 | 掌握难度 |
---|---|
无 | 普通 |
❤ | 经典,易掌握 |
❤❤ | 经典,略难掌握 |
❤❤❤ | 困难 |