面试题 33. 二叉搜索树的后序遍历序列
二叉搜索树的后序遍历序列
- 题目描述
- 示例
- 题解
- 递归
- 单调栈
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
示例
参考以下这颗二叉搜索树：
5/ \2 6/ \1 3
输入: [1,6,3,2,5]
输出: false
示例 2：
输入: [1,3,2,6,5]
输出: true
题解
递归
后序遍历的最后一个元素为根节点，根据二叉搜索树的性质，根节点左边的元素都小于根节点，根节点右边的元素都大于根节点。因此，我们找到第一个大于根节点的位置 𝑖，那么 𝑖
右边的元素都应该大于根节点，否则返回 false。然后递归判断左右子树。
class Solution {
public:bool verifyPostorder(vector<int>& postorder) {function<bool(int, int)> dfs = [&](int l, int r) -> bool {if (l >= r) {return true;}int v = postorder[r];int i = l;while (i < r && postorder[i] < v) {++i;}for (int j = i; j < r; ++j) {if (postorder[j] < v) {return false;}}return dfs(l, i - 1) && dfs(i, r - 1);};return dfs(0, postorder.size() - 1);}
};
单调栈
后序遍历的顺序为“左、右、根”，如果从右往左遍历数组，那么顺序就变成“根、右、左”，根据二叉搜索树的性质，右子树所有节点值均大于根节点值。
因此，从右往左遍历数组，就是从根节点往右子树走，此时值逐渐变大，直到遇到一个递减的节点，此时的节点应该属于左子树节点。我们找到该节点的直接父节点，那么此后其它节点都应该小于该父节点，否则返回 false。然后继续遍历，直到遍历完整个数组。
此过程借助栈来实现，具体步骤如下：
- 首先初始化一个无穷大的父节点值 𝑚𝑥，然后初始化一个空栈。
- 接下来，从右往左遍历数组，对于每个遍历到的元素 𝑥
- 如果 𝑥大于 𝑚𝑥，说明当前节点不满足二叉搜索树的性质，返回 false。
- 否则，如果当前栈不为空，且栈顶元素大于 𝑥，说明当前节点为左子树节点，循环将栈顶元素出栈并赋值给 𝑚𝑥，直到栈为空或者栈顶元素小于等于 𝑥，然后将 𝑥入栈。
遍历结束后，返回 true。
class Solution {
public:bool verifyPostorder(vector<int>& postorder) {stack<int> stk;int mx = 1 << 30;reverse(postorder.begin(), postorder.end());for (int& x : postorder) {if (x > mx) {return false;}while (!stk.empty() && stk.top() > x) {mx = stk.top();stk.pop();}stk.push(x);}return true;}
};