上海做网站找谁,成都网站营销seo电话,asp网站实例,多用户wordpress插件二叉搜索树的后序遍历序列 题目描述示例 题解递归单调栈 题目描述
输入一个整数数组#xff0c;判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true#xff0c;否则返回 false。假设输入的数组的任意两个数字都互不相同。
示例
参考以下这颗二叉搜索树#… 二叉搜索树的后序遍历序列 题目描述示例 题解递归单调栈 题目描述
输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 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(vectorint postorder) {functionbool(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(vectorint postorder) {stackint 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;}
};
