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); } }
没有评论:
发表评论