陕西有哪些公司是网站建设,像天猫网站怎么做,临沂建设公司网站,免费1级做爰片在线观看网站二叉搜索树的后序遍历序列 输入一个整数数组#xff0c;判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true#xff0c;否则返回false。
假设输入的数组的任意两个数字都互不相同。
数据范围
数组长度 [ 0 , 1000 ] [0,1000] [0,1000]。
样例
输入判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true否则返回false。
假设输入的数组的任意两个数字都互不相同。
数据范围
数组长度 [ 0 , 1000 ] [0,1000] [0,1000]。
样例
输入[4, 8, 6, 12, 16, 14, 10]输出true算法思路 基本思想 利用后序遍历特性序列最后一个元素为根节点递归验证左子树所有节点 根节点 右子树所有节点 验证过程 基准条件当子序列长度 ≤ 1 时返回true划分左右子树 定位第一个≥根节点的元素作为分界点验证右子树部分全部根节点 递归验证 左子树区间[l, k-1]右子树区间[k, r-1]排除末尾根节点 实现特点 使用类成员变量seq避免参数传递原地划分不需要额外空间
复杂度类型分析结果说明时间复杂度O(n²)最坏情况下链式树需要n(n-1)…1次比较空间复杂度O(n)递归栈深度最大为树高最坏情况下链式树为O(n)
最优情况平衡二叉树O(nlogn)最坏情况单支树O(n²)平均情况O(nlogn)
class Solution {
public:vectorint seq;bool verifySequenceOfBST(vectorint sequence) {seq sequence;return dfs(0, sequence.size() - 1);}bool dfs(int l, int r){if(l r) return true;int root seq[r];int k l;while(k r seq[k] root) k ;for(int i k 1; i r; i ){if(seq[i] root) return false;}return dfs(l, k - 1) dfs(k, r - 1);}
};算法优化方向
单调栈解法可优化至O(n)时间复杂度剪枝策略当发现非法右子树节点时立即终止递归迭代实现用栈替代递归可优化空间复杂度为O(1)尾递归优化
