【LeetCode|数据结构】剑指 Offer 33. 二叉搜索树的后序遍历序列

题目链接

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

标签

二叉搜索树、后序遍历

步骤

1. 二叉搜索树的左子树的节点值$\le$根节点值$\le$右子树的节点值；
2. 对于后序遍历序列最后一个元素的值为根节点的值；

由上面的两个性质可以得出，对于给定的后序序列 arr：

Step1. 根据 arr 的最后一个元素，将其之前的序列进行划分（左子树、右子树）；如果存在不能划分的情况，返回 false。

int flag = arr[r];
int mark = -1; // first elem > flag
for (int i = l; i < r; i++) { // check from idx:l to r-1if (arr[i] > flag) {mark = i;break;}
}
if (mark != -1) {for (int i = mark; i < r; i++) {if (arr[i] < flag) {return false;}}
} else {mark = l + 1;
}

Step2. 递归判断左右子区间，直至当前区间不能再被划分。

bool judge(vector<int> &arr, int l, int r) {if (l >= r) {return true;}/*****balabala*****/return judge(arr, l, mark-1) && judge(arr, mark, r-1);
}

完整代码（C++）

class Solution {
public:bool judge(vector<int> &arr, int l, int r) {if (l >= r) {return true;}// l <= r// step1. partitionint flag = arr[r];int mark = -1; // first elem gt flagfor (int i = l; i < r; i++) { // check from idx:l to r-1if (arr[i] > flag) {mark = i;break;}}if (mark != -1) {for (int i = mark; i < r; i++) {if (arr[i] < flag) {return false;}}} else {mark = l + 1;}return judge(arr, l, mark-1) && judge(arr, mark, r-1);}bool verifyPostorder(vector<int>& postorder) {return judge(postorder, 0, postorder.size()-1);        }
};