I think it's neat, but what about the memory? Any good ideas?


  • 0

    Any suggestions on reducing the memory use? Appreciate your time!

    public class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(inorder.length!=postorder.length||inorder.length==0) return null;
    int length=inorder.length;
    return build(inorder,postorder,0,length-1,length-1);
    }

    public TreeNode build(int[] inorder,int[] postorder,int start,int end,int postIndex){
        if(start>end)  return null;
        
        int inorderIndex=0;
        while(inorder[inorderIndex]!=postorder[postIndex])
            inorderIndex++;
        int leftNum=inorderIndex-start;
        int rightNum=end-inorderIndex;
    
        TreeNode root=new TreeNode(postorder[postIndex]);
        
        root.left=build(inorder,postorder,start,inorderIndex-1,postIndex-rightNum-1);
        root.right=build(inorder,postorder,inorderIndex+1,end,postIndex-1);
        
        return root;
    }
    

    }


  • 0
    M

    What memory is there to reduce? The only objects you seem to be making are the TreeNodes, and every one of them is needed in the solution.


  • 0

    Thank you, Mike. I need to rephrase that. I want to get rid of that while() loop but it seems impossible, any ideas on how to avoid using recursive calls? Is there any other way to solve this?(I am curious if we can find out the null nodes and build the tree without using recursive calls)


  • 0
    A

    First i also get a MLE,,the bug is that i make the index wrong,so the recursive never stop and apply too much space.I think you have the same problem.
    int inorderIndex= start; // not from 0


  • 0
    V

    I think the time complexity of this solution is O(N^2)
    and moreover we can reduce the complexity to average O(N) by hashing the values of inorder array. My observation, Time without hashing: 156ms, and with hashing: 84ms!


Log in to reply
 

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