My recursive Java code with O(n) time and O(n) space


  • 71
    L

    The the basic idea is to take the last element in postorder array as the root, find the position of the root in the inorder array; then locate the range for left sub-tree and right sub-tree and do recursion. Use a HashMap to record the index of root in the inorder array.

    public TreeNode buildTreePostIn(int[] inorder, int[] postorder) {
    	if (inorder == null || postorder == null || inorder.length != postorder.length)
    		return null;
    	HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>();
    	for (int i=0;i<inorder.length;++i)
    		hm.put(inorder[i], i);
    	return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0, 
                              postorder.length-1,hm);
    }
    
    private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe, 
                                     HashMap<Integer,Integer> hm){
    	if (ps>pe || is>ie) return null;
    	TreeNode root = new TreeNode(postorder[pe]);
    	int ri = hm.get(postorder[pe]);
    	TreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);
    	TreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);
    	root.left = leftchild;
    	root.right = rightchild;
    	return root;
    }

  • 76
    M

    This is my version: similar idea, but no HashMap needed!

    (TreeNode end is the boundary of left subtree.)

    int pInorder;   // index of inorder array
    int pPostorder; // index of postorder array
    
    private TreeNode buildTree(int[] inorder, int[] postorder, TreeNode end) {
    	if (pPostorder < 0) {
    		return null;
    	}
    	
    	// create root node
    	TreeNode n = new TreeNode(postorder[pPostorder--]);
    	
    	// if right node exist, create right subtree
    	if (inorder[pInorder] != n.val) {
    		n.right = buildTree(inorder, postorder, n);
    	}
    	
    	pInorder--;
    	
    	// if left node exist, create left subtree
    	if ((end == null) || (inorder[pInorder] != end.val)) {
    		n.left = buildTree(inorder, postorder, end);
    	}
    	
    	return n;
    }
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	pInorder = inorder.length - 1;
    	pPostorder = postorder.length - 1;
    	
    	return buildTree(inorder, postorder, null);
    }
    

  • 0
    B

    thx!!!!!!!!!!!!!!!!!!!!!


  • 0
    B

    but the global manipulation of inorder and postorder positions too very complex. Any abstract proof that this method works? (i.e. what is the invariance you assumes in each recursion)


  • 1
    S

    why define the second method as private?


  • 0
    Z

    Because of encapsulation. Imagine buildTreePostIn as an API. Clients of this API should not be able to see inner workings (i.e. implementation) of this API (to keep the API clean and/or to minimize possible dependencies); that's why buildTreePostIn(int[], int, int, int[], int, int, HashMap) is hidden.

    As a good rule of thumb: always hide everything as much as possible (i.e. make it private) until you have an exact reason to make it more visible.


  • 4
    J

    can you explain more about the index in the recursion?

    is, ri-1, postorder, ps, ps+ri-is-1,
    ri+1, ie, postorder, ps+ri-is, pe-1, 
    

    I know there will be stackOverFlowError if just use ri-1 and ri, but how do you get ps+ri-is-1 and ps+ri-is? Or can you tell me the rule of setting the index ?


  • 0
    N
    1. Find the root from postorder.
    2. Find the index of root from inverse map
    3. Find the number of elements in the left and right subtree using the index from 2 and the inorder traversal
    4. Use this information to get the correct indices in the postorder array.

  • 9
    F
    1. The post order array will give you the root, the last one.
    2. With the root, you can go to the in order array, notice the traverse sequence: left, root, right.
      Then we know the left child array size, right child array size.
    3. With the size, we can then divide the post order array: left, right, root.
      Then, we have everything!

    The beauty is the root, with the root, you are able to divide two arrays~


  • 3
    K

    Take a look at the video explanation:
    https://www.youtube.com/watch?v=k2dvEJoHVEM


  • 0
    J

    nice code!!! but can you explain in detail what your idea is behind the code?? Thanks!


  • -1
    This post is deleted!

  • 0
    M

    unbelievable codes! Anyone can explain the movement of the index?


  • 0
    9

    This technically is not O(1) space. The recursive call is still giving O(n) space. If you can covert it to iterative version then it will be O(1) space.


  • 0
    H

    wouldnt the iterative version still need space to hold information?


  • 0
    C

    C# implementation based on m29731's code

        private TreeNode BuildTree(int[] inorder, int[] postorder, TreeNode end, ref int pInorder, ref int pPostorder)
        {
            if (pPostorder < 0)
            {
                return null;
            }
    
            // create root node
            TreeNode n = new TreeNode(postorder[pPostorder--]);
    
            // if right node exist, create right subtree
            if (inorder[pInorder] != n.val)
            {
                n.right = BuildTree(inorder, postorder, n, ref pInorder, ref pPostorder);
            }
    
            pInorder--;
    
            // if left node exist, create left subtree
            if ((end == null) || (inorder[pInorder] != end.val))
            {
                n.left = BuildTree(inorder, postorder, end, ref pInorder, ref pPostorder);
            }
    
            return n;
        }
    
        public TreeNode BuildTree(int[] inorder, int[] postorder)
        {
            int pInorder = inorder.Length - 1;
            int pPostorder = postorder.Length - 1;
    
            return BuildTree(inorder, postorder, null, ref pInorder, ref pPostorder);
        }

  • 0
    B
    This post is deleted!

  • 0
    S

    I get a stackoverflow error on the line i try to retrieve the index of the root from the map. The last executed input [-1] [-1] . Can any one help?


  • 7

    Construct Binary Tree from Inorder and Postorder Traversal

        public TreeNode buildTree(int[] inorder, int[] postorder) {
          return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);    
        }
        
        TreeNode helper(int[] inorder, int[] postorder, int ppos, int is, int ie){
          if(ppos >= postorder.length || is > ie) return null;
          TreeNode node = new TreeNode(postorder[ppos]);
          int pii = 0;
          for(int i = 0; i < inorder.length; i++){
            if(inorder[i] == postorder[ppos]) pii = i;  
          }
          node.left = helper(inorder, postorder, ppos - 1 - ie + pii, is, pii - 1);
          node.right = helper(inorder, postorder, ppos - 1 , pii + 1, ie);
          return node;
        }
    

    Construct Binary Tree from Preorder and Inorder Traversal

        public TreeNode buildTree(int[] preorder, int[] inorder) {
          return helper(preorder, inorder, 0, 0, inorder.length - 1);    
        }
        
        TreeNode helper(int[] preorder, int[] inorder, int ppos, int is, int ie){
          if(ppos > preorder.length - 1 || is > ie) return null;
          TreeNode node = new TreeNode(preorder[ppos]); 
          int pipos = 0;
          for(int i = is; i <= ie; i++){
            if(inorder[i] == preorder[ppos]) pipos = i;  
          }
          node.left = helper(preorder, inorder, ppos + 1, is, pipos - 1);
          node.right = helper(preorder, inorder, ppos + 1 + pipos - is, pipos + 1, ie);
          return node;
        }

  • 0
    M

    @notsameer Why does ri-1 and r1 instead of ps+r1-is-1 and ps+ri-is lead to an error ?


Log in to reply
 

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