My Java solution [Map + Recursion!]


  • 2
    W

    Hello! I think many of the answers on here have already explained the general idea to tackling this problem. Nevertheless, this is a mirror implementation of the one that was used to convert inorder+preorder into a binary tree. The MAIN difference here is that the last index of the postorder array consists of the root node as opposed to preorder whereby the root node is starting from the first index. Since we are working backwards here, I opted to start re-attaching the right sub-trees before the left. More info can be found here!
    Feel free to let me know should you have any doubts/queries regarding the solution provided OR if this can be improved upon!

     public class Solution {
                Map<Integer, Integer> mapOfInorder = new HashMap<Integer, Integer>();
                public TreeNode buildTree(int[] inorder, int[] postorder) {
                    if(postorder.length == 0 || inorder.length == 0)
                        return null;
                    
                    buildMapOfInorder(inorder);
                    
                    return buildTreeRecursively(postorder, inorder, postorder.length-1, 0, inorder.length-1);
                }
                
                private void buildMapOfInorder(int[] inorder){
                    for(int i = 0; i < inorder.length; i++){
                        //assume no dup
                        mapOfInorder.put(inorder[i], i);
                    }
                }
                
                private TreeNode buildTreeRecursively(int[] postorder, int[] inorder, int currPreorderIndex, int startOfInorder, int endOfInorder){
                    if (currPreorderIndex < 0 || currPreorderIndex > postorder.length - 1 || startOfInorder > endOfInorder) {
                        return null;
                    }
                    int indexOfRootInInorder = mapOfInorder.get(postorder[currPreorderIndex]);
                    TreeNode root = new TreeNode(inorder[indexOfRootInInorder]);
                    //currPreorderIndex+indexOfRootInInorder-startOfInorder+1
                    
                    root.right = buildTreeRecursively(postorder, inorder, currPreorderIndex-1, indexOfRootInInorder+1, endOfInorder);
                    //To get the currPreorderIndex, we need to take the current index of and subtract it with the number of RIGHT nodes that have been traversed so far == size of list - the starting point of (curr)root.right 
                    //(+-1 due to silly indices)
                    //alternative1: currPreorderIndex-(endOfInorder-indexOfRootInInorder)-1
                    //alternative2: currPreorderIndex-((endOfInorder+1)-(indexOfRootInInorder+1))-1
                    root.left = buildTreeRecursively(postorder, inorder, currPreorderIndex-(endOfInorder+1-indexOfRootInInorder), startOfInorder, indexOfRootInInorder-1);
                    
                    return root;
                }
    

Log in to reply
 

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