原題：

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

題意很簡(jiǎn)單，根據(jù)一個(gè)先序遍歷序列和一個(gè)中序遍歷序列，生成二叉樹(shù)。這道題記得考研的時(shí)候做過(guò)很多遍，一般都是以選擇題的形式出現(xiàn)。我們將先從一個(gè)簡(jiǎn)單例子的開(kāi)始，以手工的形式來(lái)解決這個(gè)問(wèn)題，然后我們以該思路為基礎(chǔ)，用編程將其實(shí)現(xiàn)。

給定如下兩個(gè)序列：

preorder = [7, 5, 3, 6, 10, 8, 13]
inorder  = [3, 5, 6, 7, 8, 10, 13]

我們來(lái)回憶一下先序遍歷的過(guò)程，先從根節(jié)點(diǎn)出發(fā)，遍歷左子樹(shù)，左子樹(shù)遍歷完成后再遍歷右子樹(shù)。也就是說(shuō)，preorder中第一個(gè)數(shù)字7即為整棵樹(shù)根節(jié)點(diǎn)的值。再回憶下中序遍歷的過(guò)程，先遍歷左子樹(shù)，完成后遍歷根節(jié)點(diǎn)，最后遍歷右子樹(shù)。因此我們將preorder中的7在inorder中找出對(duì)應(yīng)的位置，然后7的左邊[3, 5, 6]即為左子樹(shù)的所有節(jié)點(diǎn)，7的右邊[8, 10, 13]即為右子樹(shù)的所有節(jié)點(diǎn)。我們?cè)賮?lái)分析左子樹(shù)，左子樹(shù)總共有三個(gè)節(jié)點(diǎn)，它的中序遍歷序列我們剛才已經(jīng)得出，而先序遍歷的過(guò)程是遍歷完根節(jié)點(diǎn)后，再遍歷左子樹(shù)，因此7后面的三個(gè)數(shù)[5, 3, 6]即為左子樹(shù)的先序遍歷序列。然后我們?cè)侔凑談偛艑?duì)整棵樹(shù)的分析分別對(duì)左子樹(shù)右子樹(shù)進(jìn)行分析，如此反復(fù)，直到一棵樹(shù)只剩一個(gè)節(jié)點(diǎn)為止?？吹?jīng)]有，我們?cè)僖淮斡玫搅恕胺侄沃钡乃枷搿?/p>

最后我們應(yīng)該得到這樣一幅圖：

因此根據(jù)上述分析，我們?cè)O(shè)計(jì)出如下算法：

1. 取先序列表的第一個(gè)值，創(chuàng)建根節(jié)點(diǎn)

2. 尋找根節(jié)點(diǎn)的值在中序列表中的位置m，并計(jì)算左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)n
3. 處理當(dāng)前樹(shù)的左子樹(shù)，先序列表從下一個(gè)數(shù)開(kāi)始，長(zhǎng)度為n，中序列表還是第一個(gè)數(shù)開(kāi)始，長(zhǎng)度為n，回到過(guò)程1。
4. 處理當(dāng)前樹(shù)的右子樹(shù)，先序列表為去掉左子樹(shù)后剩余的節(jié)點(diǎn)。中序列表為位置m的右半部分，回到過(guò)程1。

可能文字表述的不是很清楚，直接來(lái)看代碼吧：

class Solution {

typedef vector<int>::iterator Pos;

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

private:
    /**
     * 我們使用了一個(gè)help method來(lái)進(jìn)行遞歸構(gòu)建二叉樹(shù)
     * preBegin 先序列表的開(kāi)始節(jié)點(diǎn)
     * preEnd 先序列表的結(jié)束節(jié)點(diǎn)
     * inBegin 中序列表的開(kāi)始節(jié)點(diǎn)
     * inEnd 中序列表的結(jié)束節(jié)點(diǎn)
     */
    TreeNode* constructTree(Pos preBegin, Pos preEnd, Pos inBegin, Pos inEnd) {
        TreeNode *node = NULL;
        if (preEnd > preBegin && inEnd > inBegin) {
            int val = *preBegin; //取先序列表第一個(gè)節(jié)點(diǎn)
            node = new TreeNode(val);

            Pos mid = find(inBegin, inEnd, val); //尋找在中序列表中的位置

            int leftCount = mid - inBegin;
            //對(duì)左子樹(shù)跟右子樹(shù)分別再進(jìn)行處理
            node->left = constructTree(preBegin + 1, preBegin + 1 + leftCount, inBegin, mid);
            node->right = constructTree(preBegin + 1 + leftCount, preEnd, mid + 1, inEnd);
        }
        return node;
    }
};