Here is my O(n log n) solution. Is there any better solution accepted?


  • -1
    L

    The idea is:

    1. Find root: root must be last postorder element

    2. Search for root in inorder array. This point is the middle of two subtrees.

    Left subtree inorder elements are to the left of 'middle'. Right subtree elements are to the right of 'middle'
    For postorder elements: starting from 0 count to inorder left size. Then inorder right size. Last element (previous root) can be eliminated.

    public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        
        if (inorder.length == 0) {
            return null;
        }
        if (inorder.length == 1) {
            return new TreeNode(inorder[0]);
        }
        
        TreeNode root = findRoot(inorder, postorder);
        int middle = findMiddle(inorder, root);
        
        int[] inorderLeft = Arrays.copyOfRange(inorder, 0, middle);
        int[] inorderRight = Arrays.copyOfRange(inorder, middle+1, inorder.length);
        int[] postOrderLeft = Arrays.copyOfRange(postorder, 0, inorderLeft.length);
        int[] postOrderRight = Arrays.copyOfRange(postorder, inorderLeft.length, inorderLeft.length+inorderRight.length);
        
        root.left = buildTree(inorderLeft, postOrderLeft);
        root.right = buildTree(inorderRight, postOrderRight);
        
        return root;
    }
    
    private TreeNode findRoot(int[] inorder, int [] postorder) {
        return new TreeNode(postorder[postorder.length-1]);
    }
    
    private int findMiddle(int[] inorder, TreeNode node) {
        int middle = -1;
        for (int i=0; middle==-1;i++) {
            if (inorder[i] == node.val) {
                middle = i;
            }
        }
        return middle;
    }
    

    }


  • 9
    S

    First of all, why do you think your code runs in O(n log n)? Your findMiddle function runs in O(n). In the worst case your code runs in O(n^2) - just think of the case where inorder = [1,2,3,...,n] and postorder = [1,2,3,...,n].

    There is a O(n) solution which is based on the same observation that you have stated but avoids any explicit partitioning or "findMiddle". Basically the algorithm does the following:

    We construct nodes by iterating backwards through the inorder and postorder array.
    The main iteration is over the postorder array, creating one node for each value we encounter. We use the inorder array to determine whose child it is.

    class Solution:
    def buildTree(self, inorder, postorder):
        if len(inorder) == 0:
            return None
    
        postorder_idx = len(postorder)-1
        inorder_idx = len(inorder)-1
    
        # not strictly a parent stack
        # more of a stack of nodes whose values haven't appeared in
        # inorder yet
        parent = []
    
        # set initial node
        root = TreeNode(postorder[postorder_idx])
        postorder_idx -= 1
        
        cur = root
        while postorder_idx >= 0:
            # if we haven't seen the current value in the inorder array
            # then we know that the next node is going to be the right child
            # of the current node
            while cur.val != inorder[inorder_idx]:
                parent.append(cur)
                cur.right = TreeNode(postorder[postorder_idx])
                postorder_idx -= 1
                cur = cur.right
            
            if postorder_idx < 0:
                break
    
            inorder_idx -= 1
            
            # the next root belongs to a left subtree
            # find the correct subtree it belongs to
            while len(parent) > 0 and parent[-1].val == inorder[inorder_idx]:
                inorder_idx -= 1
                cur = parent.pop()
    
            # finally set the left subtree and continue the reconstruction
            # from there
            cur.left = TreeNode(postorder[postorder_idx])
            postorder_idx -= 1
            cur = cur.left
    
        return root

  • 0
    D

    Great! Your solution is iterative. There is another recursive solution which time complexity is O(n). Just changing the findMiddle function to HashMap and finding index will cost O(1). However, the space complexity is O(n).


Log in to reply
 

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