Construct Binary Tree From Preorder and Inorder

Description

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

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

Example
Given in-order [1,2,3] 
and pre-order [2,1,3], 
return a tree:
  2
 / \
1   3

Link

Lintcode_ladder

Method

1. Use the preorder's sequence to locate structure
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 preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        if (preorder.size() != inorder.size()) {
            return nullptr;
        }
        int plen = preorder.size();
        int ilen = inorder.size();
        return helper(preorder, 0, plen - 1, inorder, 0, ilen - 1);
    }
    TreeNode* helper(vector<int>& preorder, int pstart, int pend, 
        vector<int>& inorder, int istart, int iend
    ) {
        if (istart > iend) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[pstart]);
        int pos = getPos(preorder[pstart], inorder, istart, iend);
        // Example:
        //         1
        //    2          3
        //  4   5      7   8
        //           6
        // inorder  :   4, 2 , 5, [1], 6, 7, 3, 8
        // preorder : [1], 2 , 4,  5 , 3, 7, 6, 8
        // 
        // for the left child
        // preorder : left node from pstat + 1 -> left half part of preorder 
        // inorder : left node should be at left side of inorder
        root->left = helper(preorder, pstart + 1, pstart + pos - istart, 
                            inorder, istart, pos - 1);
        // for the right child
        // preorder : right node from right half part of preorder to end 
        // inorder : right node should be at the right side of inordre
        root->right = helper(preorder, pos - iend + pend + 1, pend, 
                             inorder, pos + 1, iend);
        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