ama-non

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

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

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

分析：

每次取preorder的第一个值mid，将其作为树的根节点
然后从inroder中找到mid，将其分割成为两部分，左边作为mid的左子树，右边作为mid的右子树

tree: 8 4 10 3 6 9 11

Inorder [3 4 6] 8 [9 10 11]

pretorder 8 [4 3 6] [10 9 11]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(begin(inorder), end(inorder), 
                         begin(preorder), end(preorder));
    }
    
    template<class T>
        TreeNode* buildTree(T in_first, T in_last, T pre_first, T pre_last) {
        if (pre_first == pre_last) return nullptr;
        if (in_first == in_last) return nullptr;
        
        const auto val = *(pre_first);
        TreeNode* root = new TreeNode(val);
        
        auto in_root_pos = find(in_first, in_last, val);
        auto left_size = distance(in_first, in_root_pos);
        auto pre_left_first = next(pre_first);
        auto pre_left_last = next(pre_left_first, left_size);
        
        root->left = buildTree(in_first, in_root_pos, 
                               pre_left_first, pre_left_last);
        root->right = buildTree(next(in_root_pos), in_last, 
                                pre_left_last, pre_last);
        
        return root;
    }
};

时间复杂度o(n),空间复杂度o(\logn)