今天分享的題目來源于 LeetCode 上的劍指 Offer 系列面試題07. 重建二叉樹，近半年在微軟面試環(huán)節(jié)出現(xiàn)過 2 次，屬于中高難度的算法題！

一、題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字。

例如，給出

前序遍歷preorder=[3,9,20,15,7] 中序遍歷inorder=[9,3,15,20,7]

返回如下的二叉樹：

3 / 920 / 157

限制：

0 <= 節(jié)點個數(shù) <= 5000

二、題目解析

首先，我們先來復習一下前序遍歷、中序遍歷。（在下方的視頻中分布講解）

前序遍歷

二叉樹的前序遍歷順序是：根節(jié)點、左子樹、右子樹，每個子樹的遍歷順序同樣滿足前序遍歷順序。

中序遍歷

二叉樹的中序遍歷順序是：左子樹、根節(jié)點、右子樹，每個子樹的遍歷順序同樣滿足中序遍歷順序。

復習過后，我們可以得出以下結(jié)論：

在二叉樹的前序遍歷序列中，第一個數(shù)字總是樹的根結(jié)點的值；

在二叉樹的中序遍歷序列中，根結(jié)點的值在序列的中間，左子樹的結(jié)點的值位于根結(jié)點的值的左邊，而右子樹的結(jié)點的值位于根結(jié)點的值的右邊

以本題的序列為例，前序遍歷序列的第一個數(shù)字 3 就是根結(jié)點的值，在中序遍歷序列，找到根結(jié)點值的位置。根據(jù)中序遍歷特點，在根結(jié)點的值 3前面的數(shù)字都是左子樹結(jié)點的值，在根結(jié)點的值 3后面的數(shù)字都是右子樹結(jié)點的值。

二叉樹很重要的一個性質(zhì)是遞歸，在找到了左子樹、右子樹的前序遍歷序列和中序遍歷序列后，我們可以按照同樣的方法去確定子左子樹和子右子樹的構(gòu)建。

具體的代碼編寫思路如下（來源于 Krahets's Blog）：

遞推參數(shù)：前序遍歷中根節(jié)點的索引pre_root_idx、中序遍歷左邊界in_left_idx、中序遍歷右邊界in_right_idx。

終止條件：當in_left_idx > in_right_idx，子樹中序遍歷為空，說明已經(jīng)越過葉子節(jié)點，此時返回 null 。

遞推工作：

建立根節(jié)點 root ：值為前序遍歷中索引為pre_root_idx的節(jié)點值。

搜索根節(jié)點 root 在中序遍歷的索引 i ：為了提升搜索效率，本題解使用哈希表map預存儲中序遍歷的值與索引的映射關(guān)系，每次搜索的時間復雜度為 O(1)。

構(gòu)建根節(jié)點root的左子樹和右子樹：通過調(diào)用 recursive()方法開啟下一層遞歸。

左子樹：根節(jié)點索引為 pre_root_idx + 1 ，中序遍歷的左右邊界分別為 in_left_idx 和 i - 1。

右子樹：根節(jié)點索引為 i - in_left_idx + pre_root_idx + 1（即：根節(jié)點索引 + 左子樹長度 + 1），中序遍歷的左右邊界分別為 i + 1 和 in_right_idx。

返回值：返回root，含義是當前遞歸層級建立的根節(jié)點root為上一遞歸層級的根節(jié)點的左或右子節(jié)點。

三、動畫描述

四、圖片描述

五、參考代碼

classSolution{ //在中序序列中查找與前序序列首結(jié)點相同元素的時候，如果使用while循環(huán)去一個個找效率很慢 //這里我們借助數(shù)據(jù)結(jié)構(gòu)HashMap來輔助查找，在開始遞歸之前把所有的中序序列的元素和它們所在的下標存到一個map中，這樣查找的時間復雜度是O(logn) HashMapmap=newHashMap<>(); //保留的前序遍歷 int[]preorder; publicTreeNodebuildTree(int[]preorder,int[]inorder){ this.preorder=preorder; //在開始遞歸之前把所有的中序序列的元素和它們所在的下標存到一個map中 for(inti=0;iin_right_idx){ returnnull; } //root_idx是在前序里面的 TreeNoderoot=newTreeNode(preorder[pre_root_idx]); //通過map，根據(jù)前序的根節(jié)點的值，在中序中獲取當前根的索引 intidx=map.get(preorder[pre_root_idx]); //左子樹的根節(jié)點就是左子樹的(前序遍歷）第一個，就是+1,左邊邊界就是left，右邊邊界是中間區(qū)分的idx-1 root.left=recursive(pre_root_idx+1,in_left_idx,idx-1); //右子樹的根，就是右子樹（前序遍歷）的第一個,就是當前根節(jié)點加上左子樹的數(shù)量 root.right=recursive(pre_root_idx+(idx-1-in_left_idx+1)+1,idx+1,in_right_idx); returnroot; } }

這段代碼的一個難點就是root.left與root.right，我這里抽離出來詳細解釋一下。

1、root.left

2、root.right

六、復雜度分析

時間復雜度

時間復雜度為 O(N)。

空間復雜度

空間復雜度為 O(N)。

七、相關(guān)標簽

樹

遞歸

哈希表

八、參考來源

1、https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/ 題解區(qū)

2、https://krahets.gitee.io/views/sword-for-offer/2020-02-24-sword-for-offer-07.html