A bottom up solution.


  • 0
    L

    This question can be solved the same as the preorder-inorder one by just reversing the postorder array, but pay a little attention, now you need to construct right child first instead of left child in the previous question. But this is still top-down recursive method. For a tree problem, you can always think the other way. So I tried a bottom-up solution. The advantage of postorder, is that, when you create a new node, both its children should be ready, so you just need to find which ones are the children of current node. I use two maps to keep the created subtrees. If you find a subtree who has a child just next to the current node in the inorder array then it will be the child of the current node.

     public TreeNode buildTree(int[] inorder, int[] postorder) {
    
            if (inorder == null || postorder == null) return null;
    
            if (inorder.length==0 || postorder.length==0) return null;
    
            if (inorder.length != postorder.length) return null;
    
            Map<Integer,TreeNodeWithRange> startMap = new HashMap<>();
    
            Map<Integer,TreeNodeWithRange> endMap = new HashMap<>();
    
            Map<Integer,Integer> inorderMap = new HashMap<>();
    
            for (int i=0; i<inorder.length; i++) {
               inorderMap.put(inorder[i],i);
            }
    
            TreeNode result = null;
            for (int i=0; i<postorder.length; i++) {
    
               TreeNode node = new TreeNode(postorder[i]);
    
               int inorderIdx = inorderMap.get(postorder[i]);
    
               TreeNodeWithRange tr = new TreeNodeWithRange();
    
               tr.node = node;
    
               tr.start = inorderIdx;
    
               tr.end = inorderIdx;
    
               TreeNodeWithRange left = endMap.get(inorderIdx-1);
    
               if (left!=null) {
                 tr.node.left = left.node;
                 tr.start = left.start;
                 endMap.remove(left.end);
                 startMap.remove(left.start);
               }
    
               TreeNodeWithRange right = startMap.get(inorderIdx+1);
               
               if(right!=null) {
                 tr.node.right = right.node;
                 tr.end = right.end;
                 startMap.remove(right.start);
                 endMap.remove(right.end);
               }
               
               startMap.put(tr.start,tr);
               endMap.put(tr.end,tr);
    
               if (i==postorder.length-1) {
                   result = node;
               }
    
            }
            
            return result;
    
     }
    
    
     private static class TreeNodeWithRange {
    
        TreeNode node;
        int start;
        int end;
     }

  • 0
    L
    This post is deleted!

  • 0
    S
    This post is deleted!

Log in to reply
 

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