My Java Solution, time complexity O(n), space complexity O(1), no stack is needed.


  • -2
    C

    Someone shows us a similar solution in the problem of Construct Binary Tree from Inorder and Postorder Traversal. I just modified his/her solution to fit this problem. The solution is very smart but also not easy to understand. But, it runs fast.

    int pInorder;
    int pPostorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    pInorder = 0;
    pPostorder = 0;
    return buildTreeHelper(preorder, inorder, null);        
    }
    
    public TreeNode buildTreeHelper(int[] preorder, int[] inorder, TreeNode end) {
    	if (pPostorder >= preorder.length)
    		return null;
    	
    	TreeNode n = new TreeNode(preorder[pPostorder++]);
    	
    	// left subtree exists
    	if (inorder[pInorder] != n.val) {
    		n.left = buildTreeHelper(preorder, inorder, n);
    }
    
    pInorder++;
    
    // right subtree exists
    if ((end == null) || (pInorder < inorder.length && inorder[pInorder] != end.val)) {
    	n.right = buildTreeHelper(preorder, inorder, end);
    }
    
    return n;
    }

  • 1
    E

    Since the algorithm uses recursion, how can you say that the space complexity is O(1), and no stack is needed?


  • 0
    C

    Thanks for your input! Yes, the stack will be needed for the recursion behind the scene. But for smart compiler, it will optimize the use of stack (reuse the stack each time the deeper level recursion is finished) to make the actual space complexity to be O(1).


  • 0

    @chaondluo Are you sure? You have two recursive buildTreeHelper calls, and after each returns, you assign its result to n.left or n.right. I don't see how that stack of nodes can be eliminated. And what about the end nodes?

    I'm not saying it's impossible, but I don't see how it could be done, and I'm not convinced the compiler can do it.


  • 0

    The poor indenting makes this rather hard to read.


Log in to reply
 

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