题目：

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?

链接： 

题解：

使用Stack来模拟preorder traversal ->   mid, left, right。主要代码都是参考了Stefan Pochmann的解答。

Time Complexity - O(n)， Space Complexity - O(logn)

public class Solution {    public boolean verifyPreorder(int[] preorder) {        int low = Integer.MIN_VALUE;        Stack
     
       stack = new Stack<>();        for(int i : preorder) {            if(i < low)                return false;            while(!stack.isEmpty() && i > stack.peek())                low = stack.pop();            stack.push(i);        }                return true;    }}
     

 

不使用Stack，Space Complexity O(1)的解法， 利用了原数组

public class Solution {    public boolean verifyPreorder(int[] preorder) {        int low = Integer.MIN_VALUE, index = -1;        for(int i : preorder) {            if(i < low)                return false;            while(index >= 0 && i > preorder[index])                low = preorder[index--];            preorder[++index] = i;        }                return true;    }}

 

 

Reference:

https://leetcode.com/discuss/51543/java-o-n-and-o-1-extra-space

https://leetcode.com/discuss/52060/72ms-c-solution-using-one-stack-o-n-time-and-space

https://leetcode.com/discuss/65241/ac-python-o-n-time-o-1-extra-space

https://leetcode.com/discuss/68862/my-c-solution-easy-to-understand