Saturday, September 5, 2015

Leetcode: 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?
Brute-force solution:
The idea to solve the problem is: a[0] must be the root of the BST. Then we start from index 1 and iterate until a number which is greater than root, mark as i. All the numbers less than i must be less than root, number greater than i must be greater than root. Then we can recursively validate the BST.


先复习一下BST,给定一个节点,其左子树的所有节点都小于该节点,右子树的所有节点都大于该节点;preorder序列是指在遍历该BST的时候,先记录根节点,再遍历左子树,然后遍历右子树;所以一个preorder序列有这样一个特点,左子树的序列必定都在右子树的序列之前;并且左子树的序列必定都小于根节点,右子树的序列都大于根节点;
根据上面的特点很容易通过递归的方式完成:
  1. 如果序列只有一个元素,那么肯定是正确的,对应只有一个节点的树;
  2. 如果多于一个元素,以当前节点为根节点;并从当前节点向后遍历,直到大于根节点的节点出现(或者到尾巴),那么根节点之后,该大节点之前的,是左子树;该大节点及之后的组成右子树;递归判断左右子树即可;
  3. 那么什么时候一个序列肯定不是一个preorder序列呢?前面得到的右子树,如果在其中出现了比根节点还小的数,那么就可以直接返回false了;

Code (Java):
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        return verifyPreorderHelper(preorder, 0, preorder.length - 1);
    }
    
    private boolean verifyPreorderHelper(int[] preorder, int lo, int hi) {
        if (lo >= hi) {
            return true;
        }
        
        int root = preorder[lo];
        int i = lo + 1;
        while (i <= hi && preorder[i] < root) {
            i++;
        }
        
        int j = i;
        while (j <= hi && preorder[j] > root) {
            j++;
        } 
        
        if (j <= hi) {
            return false;
        }
        
        return verifyPreorderHelper(preorder, lo + 1, i - 1) && 
               verifyPreorderHelper(preorder, i, hi);
    }
}

Analysis:
Time complexity O(n^2), space complexity O(1). 


Solution using two stacks:
http://segmentfault.com/a/1190000003874375

Use a stack to store the numbers less than num, and a list to store the numbers in an ascending order. If the in-order list descends, return false. 

Code (Java):
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        List<Integer> list = new ArrayList<>();
        
        for (int num : preorder) {
            if (!list.isEmpty() && num < list.get(list.size() - 1)) {
                return false;
            }
            
            while (!stack.isEmpty() && num > stack.peek()) {
                list.add(stack.pop());
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

Solution using one stack:
Since the in-order list only stores the number in ascending order. We can use a variable to store only the last i.e max value. 

Code (Java):
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        int max = Integer.MIN_VALUE;
        
        for (int num : preorder) {
            if (num < max) {
                return false;
            }
            
            while (!stack.isEmpty() && num > stack.peek()) {
                max = stack.pop();
            }
            
            stack.push(num);
        }
        
        return true;
    }
}

A constant-space solution:
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) {
            return true;
        }
        
        int i = -1;
        int max = Integer.MIN_VALUE;
        
        for (int num : preorder) {
            if (num < max) {
                return false;
            }
            
            while (i >= 0 && num > preorder[i]) {
                max = preorder[i];
                i--;
            }
            
            i++;
            preorder[i] = num;
        }
        
        return true;
    }
}

3 comments:

  1. The space complexity of the first method should be O(N)

    ReplyDelete
  2. The space of the first one should be O(logn) as it is recursion on sub tree.

    ReplyDelete
  3. The space of the first one should be O(logn) as it is recursion on sub tree.

    ReplyDelete