首页 > 代码库 > 255. Verify Preorder Sequence in Binary Search Tree
255. Verify Preorder Sequence in Binary Search Tree
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up:
Could you do it using only constant space complexity?
Hide Company Tags
Show Tags
Show Similar Problems
/* Stack time O(n)space O(n)public class Solution { public boolean verifyPreorder(int[] preorder) { //stack preorder root -left - right 先降序后升序 Stack<Integer> stack = new Stack<>(); int min = Integer.MIN_VALUE; for(int i = 0; i < preorder.length; i ++){ if(preorder[i] < min) return false; while(!stack.isEmpty() && stack.peek() < preorder[i]){ min = stack.pop(); } stack.push(preorder[i]); } return true; }}*/public class Solution { public boolean verifyPreorder(int[] preorder) { int i = -1; int min = Integer.MIN_VALUE; for(int num : preorder){ if(num < min) return false; while(i >= 0 && preorder[i] < num){ min = preorder[i--]; } preorder[++i] = num; } return true; }}
Follow up 参考 https://segmentfault.com/a/1190000003874375
如何验证中序序列？A：中序序列是有序的，只要验证其是否升序的就行了。
如何验证后序序列？
后序序列的顺序是left - right - root，而先序的顺序是root - left - right。我们同样可以用本题的方法解，不过是从数组的后面向前面遍历，因为root在后面了。而且因为从后往前看是先遇到right再遇到left，所以我们要记录的是限定的最大值，而不再是最小值，栈pop的条件也变成pop所有比当前数大得数。栈的增长方向也是从高向低了。
public static boolean verifyPostorder(int[] preorder) { int i = preorder.length; int max = Integer.MAX_VALUE; for(int j = preorder.length -1; j >=0; j--){ if(preorder[j] > max) return false; while(i < preorder.length && preorder[i] < preorder[j]){ max = preorder[i++]; } preorder[--i] = preorder[j]; } return true; }
255. Verify Preorder Sequence in Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。