2015年11月2日星期一

Verify Preorder Sequence in Binary Search Tree leetcode

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.
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        return helper(preorder, 0, preorder.length - 1);
    }
    public boolean helper(int[] preorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int i = left + 1;
        while (i <= right && preorder[i] < preorder[left]) {
            i++;
        }
        int j = i;
        while (j <= right) {
            if (preorder[j] > preorder[left]) {
                j++;
            } else {
                return false;
            }
        }
        
        return helper(preorder, left + 1, i - 1) && helper(preorder, i, right);
        
    }
}

没有评论:

发表评论