Construct Binary Tree from Preorder and Inorder Traversal

LeetCode #105

Description:

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

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

Example:

Let us consider the below traversals:

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

                 A
               /   \
             /       \
           D B E     F C

Idea:

Preorder sequence: 
A B D E C F
^ ~~~~~ ---

Inorder sequence: 
D B E A F C
~~~~~ ^ ---

preorder第一个就是root，在inorder里找到这个，然后从inorder里找出left tree的size和right tree的size。递归。

Code:

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }

    // Use iterator, left inclusive [pre_begin, pre_end)

    template<typename T>
    TreeNode* buildTree(T pre_begin, T pre_end, T in_begin, T in_end){
        if(pre_begin==pre_end) return NULL; // 到底了，return NULL
        if(in_begin==in_end) return NULL;

        TreeNode* root = new TreeNode(*pre_begin);
        auto it_root_inorder = find(in_begin, in_end, *pre_begin);
        int left_size = it_root_inorder-in_begin; // Left subtree size
        int right_size = in_end-it_root_inorder-1; // right subtree size

        root->left = buildTree(next(pre_begin, 1), next(pre_begin, left_size+1), in_begin, it_root_inorder);
        root->right = buildTree(next(pre_begin, left_size+1), pre_end, next(it_root_inorder, 1), in_end);

        return root;
    }
};