My Accepted Java Solution


  • 156
    J

    Hi guys, this is my Java solution. I read this post, which is very helpful.

    The basic idea is here:
    Say we have 2 arrays, PRE and IN.
    Preorder traversing implies that PRE[0] is the root node.
    Then we can find this PRE[0] in IN, say it's IN[5].
    Now we know that IN[5] is root, so we know that IN[0] - IN[4] is on the left side, IN[6] to the end is on the right side.
    Recursively doing this on subarrays, we can build a tree out of it :)

    Hope this helps.

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0, 0, inorder.length - 1, preorder, inorder);
    }
    
    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0; // Index of current root in inorder
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
            }
        }
        root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
        root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
        return root;
    }
    

  • 0
    S

    Thanks. Very intuitive solution!


  • 15
    W

    Should there be a "break;" after "inIndex = i;" ?


  • 0
    M

    Hi, what's the running time of your code?


  • 3
    Y

    According to the article(see link below), the time is dependent on the search index of in-order sequence for each node. the average case running time is NlogN (when the tree is balanced), worst case is N^2(when the tree is skewed to left or right).
    Article link: http://articles.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html


  • 8
    Y

    Thanks!
    I also cooked the solution of a similar problem "Construct Binary Tree from Postorder and Inorder Traversal" according to your solution.

    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	return buildTreeInPost(postorder.length-1, 0, inorder.length-1, postorder, inorder);	
    }
    private TreeNode buildTreeInPost(int postStart, int inStart, int inEnd, int[] postorder, int[] inorder) {
    	if(inStart>inEnd ||postStart<0) return null;
    	TreeNode root = new TreeNode(postorder[postStart]);
    	
    	int inIndex = 0;
    	for (int i=inStart; i<=inEnd; i++) {
    		if(inorder[i] == root.val){
    			inIndex = i;
    			break;
    		}
    	}
    	root.left = buildTreeInPost(postStart-(inEnd-inIndex)-1, inStart, inIndex-1, postorder, inorder);
    	root.right = buildTreeInPost(postStart-1, inIndex+1, inEnd, postorder, inorder);	
    	
    	return root;
    }
    

  • 38
    S

    Same idea, but easier to understand.

     public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length!=inorder.length) return null;
        return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }
    
    public TreeNode build(int [] preorder, int preLow, int preHigh, int[] inorder, int inLow, int inHigh){
        if(preLow>preHigh || inLow>inHigh) return null;
        TreeNode root = new TreeNode(preorder[preLow]);
       
        int inorderRoot = inLow;
        for(int i=inLow;i<=inHigh;i++){
            if(inorder[i]==root.val){ inorderRoot=i; break; }
        }
       
        int leftTreeLen = inorderRoot-inLow;
        root.left = build(preorder, preLow+1, preLow+leftTreeLen, inorder, inLow, inorderRoot-1);
        root.right = build(preorder, preLow+leftTreeLen+1, preHigh, inorder, inorderRoot+1, preHigh);       
        return root;        
    }

  • 1

    Actually the code for finding preorder[preStart] in inorder[] can be simpler. Here is my concise code in Java.

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(preorder, 0, inorder, 0, inorder.length - 1);
    }
    
    public static TreeNode helper(int[] preorder, int preStart, int[] inorder, int inStart, int inEnd) {
        if (preStart > preorder.length - 1 || inStart > inEnd)
            return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int target = inStart;
        while (inorder[target] != preorder[preStart]) target++;
        root.left = helper(preorder, preStart + 1, inorder, inStart, target - 1);
        root.right = helper(preorder, preStart + target - inStart + 1, inorder, target + 1, inEnd);
    
        return root;
    }

  • 84

    Nice solution! One improvement: remember to use HashMap to cache the inorder[] position. This can reduce your solution from 20ms to 5ms.

    Here is the my Java solution:

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();
    
        for(int i = 0; i < inorder.length; i++) {
            inMap.put(inorder[i], i);
        }
    
        TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
        return root;
    }
    
    public TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
        if(preStart > preEnd || inStart > inEnd) return null;
    
        TreeNode root = new TreeNode(preorder[preStart]);
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart;
    
        root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
        root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorder, inRoot + 1, inEnd, inMap);
    
        return root;
    }

  • -1
    This post is deleted!

  • 0
    R

    You can remove preEnd. It's not used for anything.


  • 3
    W

    The testing data is imbalanced.

    After changing

    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == root.val) {
            inIndex = i;
        }
    }
    

    to

    for (int i = inEnd; i >= inStart; i--) {
        if (inorder[i] == root.val) {
            inIndex = i;
            break;
        }
    }
    

    The running time is from 19ms to 2ms.


  • 2
    L

    Can anyone tell me why preStart + inIndex - inStart + 1 for the preStart of the right tree? It looks to me preStart and inStart should always be equal, so both should be inIndex + 1. In fact, if we start with preStart = inStart = 0, then preStart + inIndex - inStart + 1 always equal to inIndex + 1 anyways


  • 0
    T

    @small_box: shouldn't last line be inHigh instead of preHigh. It breaks the symmetry.

        root.right = build(preorder, preLow+leftTreeLen+1, preHigh, inorder, inorderRoot+1, inHigh);
    

  • 0
    N
    This post is deleted!

  • 0
    S

    @wz366 Nice catch! I'm wondering the same thing. :)


  • 0
    S

    @yavinci Elegant! Couldn't be more beautiful! Wish I could upvote yours twice.


  • 0
    S

    @yellowstone Hi, I really like your solution, but just for my understanding, I think the first variable in your recursion function should be renamed to postEnd, right? as it denotes the end index of the postorder array. Please correct me if I'm wrong.
    Thanks.


  • 0
    R

    root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);

    Can anyone explain, why -inStart is needed in above line?
    I am keep thinking that preStart+inIndex+1 will give the index of right side of the root, cannot figure it out, why -inStart is needed.

    Thanks in adv.


  • 1

    @wddd
    i have to say lol
    good job man


Log in to reply
 

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