題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷虛列{4,7,2,1,5,3,8,6}，則重建出如下圖二叉樹并輸出它的頭結(jié)點(diǎn)。

二叉樹結(jié)點(diǎn)定義為：

思路：

本題的考點(diǎn)是樹的前序遍歷和中序遍歷，以及用遞歸方法來構(gòu)建樹。

通過畫圖觀察可知，對(duì)于每一個(gè)樹（子樹），給出前序遍歷和中序遍歷序列，前序遍歷的第一個(gè)值就是樹的根結(jié)點(diǎn)，題干里又說，不含有重復(fù)數(shù)字，因此通過確定根結(jié)點(diǎn)在中序遍歷序列里的位置，即可得知左子樹和右子樹結(jié)點(diǎn)序列。中序遍歷序列根結(jié)點(diǎn)左側(cè)的結(jié)點(diǎn)屬于它的左子樹，右側(cè)的結(jié)點(diǎn)屬于右子樹。對(duì)于每一個(gè)子樹，傳遞其前序遍歷序列和中序遍歷序列，就可以用同樣的方法確定左右結(jié)點(diǎn)。

因此，可以遞歸調(diào)用樹的結(jié)點(diǎn)構(gòu)造方法，方法參數(shù)為前序遍歷序列、中序遍歷序列、前序遍歷中（子）樹的開始位置和結(jié)束位置，中序遍歷中（子）樹的開始位置和結(jié)束位置。

終止條件：

當(dāng)傳遞的序列只有一個(gè)值，則可以確定該結(jié)點(diǎn)為葉子結(jié)點(diǎn)，不再含有子結(jié)點(diǎn)。

特殊情況：

傳入的序列為空，或者前序遍歷和中序遍歷序列不匹配等，需要加以考慮

代碼如下：