105. Construct Binary Tree from Preorder and Inorder Traversal

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:

    3
   / \
  9  20
    /  \
   15   7

---

根据树的先序遍历和中序遍历结果，重构这棵树。 其实大学的时候就有这样的作业，如果在纸上做，还是很简单的，但要实现成代码，稍微有点难理清这里的关系。 我们先来看一个纸上的解题过程，假设有下面这样一棵树：

        3
     /     \
    9       20
  /  \     /   \
 1    2  15    17

• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

首先我们可以根据先序遍历结果找到根节点3，然后在中序遍历中看看3所处的位置，那么3左边的就是左孩子节点，右边的就是右孩子节点。我们在中序遍历中看看3左边有3个节点，说明3的左子树共有3个节点，同理右子树有3个节点。所以我们在先序遍历中也能知道3后面的3个节点是左子树，再后面3个节点是右子树，这样就把两个遍历结果分成了两部分：

• 先序遍历结果为：3, 9, 1, 2, 20, 15, 17
• 中序遍历结果为：1, 9, 2, 3, 15, 20, 17

在红色部分递归就是3的左子树，在蓝色部分递归就是3的右子树。 纸上解题好说，但是代码实现，我开始还把自己搞糊涂了，代码很复杂，后来参考了这位大神的博客，代码好简洁易懂，赞一个：

class Solution {
private:
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int preL, int preR, int inL, int inR, unordered_map<int, size_t>& hash)
    {
        if (preL > preR || inL > inR)
            return NULL;
        TreeNode* root = new TreeNode(preorder[preL]);
        size_t idx = hash[root->val];
        root->left = dfs(preorder, inorder, preL + 1, idx – inL + preL, inL, idx – 1, hash);
        root->right = dfs(preorder, inorder, idx – inL + preL + 1, preR, idx + 1, inR, hash);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        if (preorder.size() == 0)
            return NULL;
        unordered_map<int, size_t> hash;
        for (size_t i = 0; i < inorder.size(); ++i) {
            hash[inorder[i]] = i;
        }
        return dfs(preorder, inorder, 0, preorder.size() – 1, 0, inorder.size() – 1, hash);
    }
};

本代码提交AC，用时16MS。
代码中有两点需要注意的，一是为了在中序遍历中快速找到根节点，提前对中序遍历结果hash了，因为题目中说了不会有重复元素；二是在dfs递归的时候，要算好下标的起止位置，一定不要弄错了，特别是preorder在左右子树中的起止位置。