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

思路

方法一：递归

1.最后一个节点为根节点
2.左边的节点全部要小于根，右边的节点全部要大于根，因此数组可以分成两个区间，前半部分全部小于根，后半部分全部大于根
3.找到两个区间的分割点，判断是否两个区间是否符合该性质

 1 class Solution {
 2 public:
 3     bool verifyPostorder(vector<int>& postorder) {
 4         if(postorder.empty()) {
 5             return true;
 6         }
 7 
 8         return check(postorder, 0, postorder.size()-1);
 9     }
10 
11 
12     bool check(vector<int>& postorder, int L, int R) {
13         if(L >= R)  
14             return true;
15 
16         /*根据二叉搜索树的性质：左子树小于根节点的值*/
17         int i;
18         //找到第一个大于根节点的值的下标i
19         for(i = L; i < R; ++i) {
20             if(postorder[i] > postorder[R]) {
21                 break;
22             }
23         }
24 
25         /*右子树大于根节点的值*/
26         for(int j = i+1; j < R; ++j) {
27             if(postorder[j] < postorder[R])
28                 return false;
29         }
30 
31         //递归检查左右子树是否满足二叉搜索树的性质
32         return check(postorder, L, i-1) && check(postorder, i, R-1);
33     }
34 };

复杂度分析

时间复杂度 O(N^2)：每次递归调用都减去一个根节点，因此递归占用 O(N) ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N) 。
空间复杂度 O(N) ：最差情况下（即当树退化为链表），递归深度将达到 N 。

方法二：辅助栈

面试题33. 二叉搜索树的后序遍历序列（递归分治 / 单调栈，清晰图解）

递归和栈两种方式解决，最好的击败了100%的用户