Four Lines Solution & Anther O(1) space solution without abusing the given array


  • 0
    O

    4Lines Reference

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

    public boolean verifyPreorder(int[] pre) {
            int i, j, n = pre.length, minBd = Integer.MIN_VALUE;
            for (i = 1, j = 0; i < n && pre[i] > minBd; pre[++j] = pre[i++])
                for (; j >= 0 && pre[j] < pre[i]; minBd = pre[j--]);
            return i >= n;
        }
    

    Anther O(1) space solution without abusing the given array:

    Each time when you encounter a preorder[i] > preorder[i - 1], you know you are going to right branch, and you need to update the min boundary for that right sub tree. The min boundary is the local parent of that right sub tree, the value is indeed equals to the largest preorder element among [0 ~ i - 1] while smaller than preorder[i].

    public class Solution {
        public boolean verifyPreorder(int[] preorder) {
            int min = Integer.MIN_VALUE, n = preorder.length, j, i, k;
            for (i = 1; i < n && preorder[i] > min; i++) 
                if (preorder[i - 1] < preorder[i]) {
                    for (k = i - 1, j = i - 2; j >= 0; j--)
                        if (preorder[j] < preorder[i] && preorder[j] > preorder[k]) k = j;
                    min = preorder[k]; 
                }
            return i >= n;
        }
    }

  • 0
    T

    Although your answer might be valid (I haven't look deeply), your time complexity is O(N^2) instead of O(N) as essentially you're scanning right to left each time. The stack helps you store the next higher subtree root which is essential to this problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.