Time Limit Exceeded


  • 2
    W

    The simliar method has used to sovle the problem in preOrder and inOrder.It is really accepted.When I use the method in this situation.Time Limit Exceeded...Why?

    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
           return  helper(postorder.length-1,0,inorder.length-1,inorder,postorder);
        }
        public TreeNode helper(int preend,int instart,int inend,int[] inorder,int[] postorder){
            if(instart>inend||preend<0) return null;
            TreeNode head = new TreeNode(postorder[preend]);
            int index=0;
            for(int i=instart;i<=inend;i++){
                if(inorder[i]==head.val){
                    index=i;
                }
            }
            head.left= helper(preend-index-1+instart,instart,index-1,inorder,postorder);
            head.right=helper(preend-1,index+1,inend,inorder,postorder);
            return head;
        }
    }

  • 0
    Z

    same here...


  • 0
    C

    did you find out how to solve it? I met the same problem that is the same as yours.


  • 0
    W

    yes,I got the accepted answer below:

    head.left= helper(preend-inend+index-1,instart,index-1,inorder,postorder);

  • 0
    Y

    The root.left line original post is equivalent to

    root.left = buildTreeInPost(postStart-(inIndex-inStart)-1, inStart, inIndex-1, postorder, inorder);
    

    and the correct one (which is in the comment) is equivalent to

    root.left = buildTreeInPost(postStart-(inEnd-inIndex)-1, inStart, inIndex-1, postorder, inorder);
    

    Reason: for postorder, we should use inEnd as reference.
    we can also demonstrate this with an example in link http://articles.leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html.

    Inorder: 4,10,3,1,7,11,8,2

    postorder: 4,1,3,10,11,8,2,7

    Using the wrong root.left line, the left and right node of root is 3 and 2. Using the correct root.left line, the left and right node of root is 10 and 2.


Log in to reply
 

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