A bottom up solution.

  • 0

    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++) {
            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;
               TreeNodeWithRange right = startMap.get(inorderIdx+1);
               if(right!=null) {
                 tr.node.right = right.node;
                 tr.end = right.end;
               if (i==postorder.length-1) {
                   result = node;
            return result;
     private static class TreeNodeWithRange {
        TreeNode node;
        int start;
        int end;

  • 0
    This post is deleted!

  • 0
    This post is deleted!

Log in to reply

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