Construct Binary Tree From Inorder and Postorder

Description

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

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

Example
Given inorder [1,2,3] 
and postorder [1,3,2], 
return a tree:
  2
 / \
1   3

Link

Lintcode_ladder

Method

1. Use post-order sequence to locate the pos.
2. x

Example

1. 1

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    /**
     *@param inorder : A list of integers that inorder traversal of a tree
     *@param postorder : A list of integers that postorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        // write your code here
        if (inorder.empty() || inorder.size() != postorder.size()) {
            return nullptr;
        }
        int ilen = inorder.size();
        int plen = postorder.size();
        return helper(inorder, 0, ilen - 1, postorder, 0, plen - 1);
    }
    TreeNode* helper(vector<int>& inorder, int istart, int iend,
        vector<int>& postorder, int pstart, int pend
    ) {
        if (istart > iend) {
            return nullptr;
        }    
        TreeNode* root = new TreeNode(postorder[pend]);
        int pos = getPos(postorder[pend], inorder, istart, iend);
        // Example:
        //         1
        //    2          3
        //  4   5      7   8
        //           6
        // inorder  :   4, 2 , 5, [1], 6, 7, 3,  8
        // postorder :  4, 5 , 2,  6 , 7, 8, 3, [1]
        // Notice : postorder can be seen as the reversed sequerence of preorder
        // left node
        root->left = helper(inorder, istart, pos - 1,
                            postorder, pstart, pstart + pos - istart - 1);
        // right node
        root->right = helper(inorder, pos + 1, iend, 
                             postorder, pstart + pos - istart, pend - 1);
        return root;
    }
    int getPos(int target, vector<int>& inorder, int istart, int iend) {
        for (int i = istart; i <= iend; ++i) {
            if (inorder[i] == target) {
                return i;
            }
        }
        return -1;
    }
};

Similar problems

x

Tags

x