wordpress建站博客,青岛全网营销推广,申请商标注册,网站域名怎么起文章目录题目描述思路 代码1. 递归做法2. 辅助栈做法二刷打卡第四天#xff5e;昨天没来得及写博客 题目描述
无须多言#xff0c;直接冲思路吧#xff01;
思路 代码
1. 递归做法
缺点#xff1a;最差情况下#xff0c;可能会退化成链表 代码1. 递归做法2. 辅助栈做法二刷打卡第四天昨天没来得及写博客 题目描述
无须多言直接冲思路吧
思路 代码
1. 递归做法
缺点最差情况下可能会退化成链表导致时间复杂度变成 O(n2n^2n2)但是比较好理解对于当前序列根据末尾元素值来找左子树范围 右子树范围然后分别递归进行判断即可
class Solution {public boolean verifyPostorder(int[] postorder) {// 递归法return isTree(postorder, 0, postorder.length - 1);}public boolean isTree(int[] postorder, int start, int end) {// 找完了if (start end) {return true;}int left start;// 找左子树while(left end postorder[left] postorder[end]) {left;}// 找右子树int right left;while(right end postorder[right] postorder[end]) {right;}// 右子树临接根才行return right end isTree(postorder, start, left - 1) isTree(postorder, left, right - 1);}
}2. 辅助栈做法
相对于上一个做法这里把时间复杂度稳定在O(nnn)同时做了空间复杂度O(n)的牺牲可以结合这个大佬的题解一起理解有图还是比较便于理解的这个做法一开始可能有点难理解可以多跟着画几次图理一理
class Solution {// 辅助栈法public boolean verifyPostorder(int[] postorder) {// 初始化把postorder[len - 1]看成无穷的左结点StackInteger stack new Stack();int root Integer.MAX_VALUE;// 逆向变成 根 - 右 - 左 的遍历for(int i postorder.length - 1; i 0; i--) {// 左子树结点不能比根 or 根的右子树结点大if(postorder[i] root) {return false;}// 找到大于当前结点的栈值while(!stack.isEmpty() stack.peek() postorder[i]) {// 循环结束时找到 root途中pop掉的结点无后效性root stack.pop();}stack.push(postorder[i]);}return true;}
}二刷
class Solution {public boolean verifyPostorder(int[] postorder) {return judge(postorder, 0, postorder.length - 1);}public boolean judge(int[] postorder, int left, int right) {if(left right) {return true;}int leftEnd left;while(leftEnd right postorder[leftEnd] postorder[right]) {leftEnd;}int rightEnd leftEnd;while(rightEnd right postorder[rightEnd] postorder[right]) {rightEnd;}return rightEnd right judge(postorder, left, leftEnd - 1) judge(postorder, leftEnd, rightEnd - 1);}
}辅助栈做法先鸽着以后有空写。
