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

一、題目描述

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

例如，給出

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

返回如下的二叉樹(shù)：

3 / 920 / 157

限制：

0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 5000

二、題目解析

首先，我們先來(lái)復(fù)習(xí)一下前序遍歷、中序遍歷。（在下方的視頻中分布講解）

前序遍歷

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

中序遍歷

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

復(fù)習(xí)過(guò)后，我們可以得出以下結(jié)論：

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

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

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

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

具體的代碼編寫(xiě)思路如下（來(lái)源于 Krahets's Blog）：

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

終止條件：當(dāng)in_left_idx > in_right_idx，子樹(shù)中序遍歷為空，說(shuō)明已經(jīng)越過(guò)葉子節(jié)點(diǎn)，此時(shí)返回 null 。

遞推工作：

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

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

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

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

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

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

三、動(dòng)畫(huà)描述

四、圖片描述

五、參考代碼

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

這段代碼的一個(gè)難點(diǎn)就是root.left與root.right，我這里抽離出來(lái)詳細(xì)解釋一下。

1、root.left

2、root.right

六、復(fù)雜度分析

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度為 O(N)。

空間復(fù)雜度

空間復(fù)雜度為 O(N)。

七、相關(guān)標(biāo)簽

樹(shù)

遞歸

哈希表

八、參考來(lái)源

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