LeetCode: 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.

---

The same idea as the previous problem. The root node for the tree is the last element of postorder list.

C++ Code:

/*
 * func: build_tree_postorder_inorder_helper
 * goal: helper function to build tree
 * @param postorder: preorder traversal list
 * @param post_start: starting index
 * @param post_end: ending index
 * @param inorder: inorder traversal list
 * @param in_start: starting index for inorder
 * @param in_end: ending index for inorder
 * return: root node
 */
TreeNode *build_tree_postorder_inorder_helper(vector<int> &postorder, int post_start, int post_end,
                                             vector<int> &inorder, int in_start, int in_end){
    if(in_start > in_end){
        return nullptr;
    }
    
    TreeNode *root;
    int i;
    //Find the root node in inorder list
    for(i = in_start; i <= in_end; i++)
        if(inorder[i] == postorder[post_end])
            break;
    
    root = new TreeNode(inorder[i]);
    if(i > in_start)
        root->left = build_tree_postorder_inorder_helper(postorder, post_start, post_end-1-in_end+i, inorder, in_start, i-1);
    if(i < in_end)
        root->right = build_tree_postorder_inorder_helper(postorder, post_end - i, post_end-1, inorder, i+1, in_end);
    
    return root;
}
/*
 * func: build_tree_postorder_inorder
 * goal: build the tree from the postorder and inorder traversal of the tree
 * @param preorder: preorder list of the tree
 * @param inorder: inorder list of the tree
 * return: root node of the tree
 */
TreeNode *build_tree_postorder_inorder(vector<int> &preorder, vector<int> &inorder){
    if(postorder.size() == 0){
        return nullptr;
    }
    
    return build_tree_preorder_inorder_helper(postorder, 0, postorder.size()-1, inorder, 0, inorder.size()-1);
}

Python Code:

# func: construct tree from post order and in order
# @param postorder: postorder traversal list
# @param inorder: inorder traversal list
# @return: root node
def build_tree_postorder_inorder(postorder, inorder):
    if not inorder:
        return None
    root = TreeNode(postorder[-1])
    id = inorder.index(postorder[-1])
    root.left = build_tree_postorder_inorder(postorder[:id], inorder[:id])
    root.right = build_tree_postorder_inorder(postorder[id:-1], inorder[id+1:])

    return root