1.題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

2.算法分析
首先，我們要理解什么是前序和中序遍歷。在二叉樹的前序遍歷序列中，第一個數(shù)字一定是樹的根結(jié)點的值，然后是左子樹、右子樹。而在中序遍歷序列中，根結(jié)點的值一定在序列的中間，根節(jié)點左側(cè)為左子樹的結(jié)點的值，根節(jié)點右側(cè)為右子樹的結(jié)點的值。

因此，這個題目的解題思路就是掃描中序遍歷序列，找到根結(jié)點的值，然后根據(jù)根節(jié)點的位置，找到左、右子樹的前序遍歷序列和中序遍歷序列，用同樣的方法分別去構(gòu)建左右子樹，即采用遞歸的形式完成。

3.代碼實例