[leetcode] Verify Preorder Sequence in Binary Search Tree

recursion方法很简单
但O（n)的思路实在太烧脑了，
貌似还有神人不用stack就做出来的... 我还是规规矩矩用两个stack吧
下次看回这里 心里想一棵树 然后想想inorder 和temp的运作就可以pick up回现在的思路了

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public class Solution { public boolean verifyPreorder(int[] preorder) { Stack<Integer> inorder = new Stack<Integer>(); Stack<Integer> temp = new Stack<Integer>(); for (int i = 0; i < preorder.length; i++){ if (!inorder.isEmpty()&&preorder[i] < inorder.peek()){ return false; } while (!temp.isEmpty() && temp.peek() < preorder[i]){ inorder.push(temp.pop()); } temp.push(preorder[i]); } return true; } }