leetcode Question 20: Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Analysis:

An easy solution is scan from the last element to the 1st element of the postorder vector. For each element, search the position in inorder vector, and place the element in a proper position of the tree. However, this method is time consuming, which cannot pass the large test.
Another idea is to use the recursion.
1. Find the last node in the postorder vector, which is the root of the current tree.
2. Find the position of root node in the inorder vector, which divide the inorder vector into 2 sub tree inorder vectors. Left part is the left sub-tree, right part is the right sub-tree.
3. Do 1 and 2 for the right and left sub-tree, respectively.
(Updated in 201309)
e.g. The tree is:
        1
   2        3
4   5         6
Inorder:         425136
Postorder:     452631

So, first we have 1 as the root node,  and find 1's position in inorder,   425   1    36
Then we search    inorder 36              as the right child,     and      inorder:    425    as the left child
                           postorder (452)63                                            postorder: 452

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *ct(vector<int> &inorder, vector<int> &postorder, int ist, int ied, int ped) {    
            if (ist>ied){return NULL;}
            TreeNode *res=new TreeNode(postorder[ped]);
            int mid;
            for (int i=ist;i<=ied;i++){
                if (inorder[i]==res->val){mid = i;break;}
            }
            res->right = ct(inorder,postorder,mid+1,ied,ped-1);
            res->left = ct(inorder,postorder,ist,mid-1, ped-1-ied+mid);
            return res;
    }


    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (postorder.size()==0){
            return NULL;
        }else{
            return ct(inorder,postorder,0,inorder.size()-1,postorder.size()-1);
        }
            
    }    
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param inorder, a list of integers
    # @param postorder, a list of integers
    # @return a tree node
    
    def newTree(self, ind, postd):
        if len(postd) == 0:
            return None
        root = TreeNode(postd[-1]) #get root node from postorder
        idx = ind.index(postd[-1]) #get root node index in inorder
        rlen = len(ind[idx+1:])  #length of the right subtree
        llen = len(ind) - rlen - 1 #length of the left subtree
        if rlen > 0:
            # get inorder right part and postorder last rlen elements
            root.right = self.newTree(ind[idx+1:], postd[-(rlen+1):-1])
        if llen > 0:
            # get inorder left part and postorder first llen elements
            root.left = self.newTree(ind[0:idx], postd[0:llen])
        return root
    
    def buildTree(self, inorder, postorder):
        return self.newTree(inorder, postorder)