重建二叉樹(shù)

輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)構(gòu)建該二叉樹(shù)并返回其根節(jié)點(diǎn)。

假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

示例1

• Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

• Output: [3,9,20,null,null,15,7]

示例2

• Input: preorder = [-1], inorder = [-1]

• Output: [-1]

限制

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

方法一：遞歸

思路

• 前序遍歷：【根節(jié)點(diǎn) | 左子樹(shù) | 右子樹(shù)】

• 中序遍歷：【左子樹(shù) | 根節(jié)點(diǎn) | 右子樹(shù)】

只要我們?cè)谥行虮闅v中定位到根節(jié)點(diǎn)，那么我們就可以分別知道左子樹(shù)和右子樹(shù)中的節(jié)點(diǎn)數(shù)目。由于同一顆子樹(shù)的前序遍歷和中序遍歷的長(zhǎng)度顯然是相同的，因此我們就可以對(duì)應(yīng)到前序遍歷的結(jié)果中，對(duì)上述形式中的所有左右括號(hào)進(jìn)行定位。

這樣，我們就知道了左子樹(shù)的前序遍歷和中序遍歷結(jié)果，以及右子樹(shù)的前序遍歷和中序遍歷結(jié)果，我們就可以遞歸地對(duì)構(gòu)造出左子樹(shù)和右子樹(shù)，再將這兩顆子樹(shù)接到根節(jié)點(diǎn)的左右位置。

細(xì)節(jié)

在中序遍歷中對(duì)根節(jié)點(diǎn)進(jìn)行定位時(shí)，一種簡(jiǎn)單的方法是直接掃描整個(gè)中序遍歷的結(jié)果并找出根節(jié)點(diǎn)，但這樣做的時(shí)間復(fù)雜度較高。我們可以考慮使用哈希表來(lái)幫助我們快速地定位根節(jié)點(diǎn)。

對(duì)于哈希映射中的每個(gè)鍵值對(duì)，鍵表示一個(gè)元素（節(jié)點(diǎn)的值），值表示其在中序遍歷中的出現(xiàn)位置。在構(gòu)造二叉樹(shù)的過(guò)程之前，我們可以對(duì)中序遍歷的列表進(jìn)行一遍掃描，就可以構(gòu)造出這個(gè)哈希映射。

在此后構(gòu)造二叉樹(shù)的過(guò)程中，我們就只需要 O(1)的時(shí)間對(duì)根節(jié)點(diǎn)進(jìn)行定位了。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 是樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)。

• 空間復(fù)雜度：O(n)，除去返回的答案需要的 O(n) 空間之外，我們還需要使用 O(n) 的空間存儲(chǔ)哈希映射，以及 O(h)（其中 h 是樹(shù)的高度）的空間表示遞歸時(shí)?？臻g。這里 h < n，所以總空間復(fù)雜度為 O(n)。

方法二：迭代

思路

• 前序遍歷，從根節(jié)點(diǎn)root開(kāi)始，只要有左子節(jié)點(diǎn)，就一直會(huì)往左下方走，直到最左下角。

• 中序遍歷，是從最左下角往上，如果碰到節(jié)點(diǎn)有右子節(jié)點(diǎn)，則會(huì)轉(zhuǎn)向。

算法

我們用一個(gè)棧和一個(gè)指針輔助進(jìn)行二叉樹(shù)的構(gòu)造。初始時(shí)棧中存放了根節(jié)點(diǎn)（前序遍歷的第一個(gè)節(jié)點(diǎn)），指針指向中序遍歷的第一個(gè)節(jié)點(diǎn)；

我們依次枚舉前序遍歷中除了第一個(gè)節(jié)點(diǎn)以外的每個(gè)節(jié)點(diǎn)。如果 index 恰好指向棧頂節(jié)點(diǎn)，那么我們不斷地彈出棧頂節(jié)點(diǎn)并向右移動(dòng) index，并將當(dāng)前節(jié)點(diǎn)作為最后一個(gè)彈出的節(jié)點(diǎn)的右兒子；如果 index 和棧頂節(jié)點(diǎn)不同，我們將當(dāng)前節(jié)點(diǎn)作為棧頂節(jié)點(diǎn)的左兒子。

無(wú)論是哪一種情況，我們最后都將當(dāng)前的節(jié)點(diǎn)入棧。

最后得到的二叉樹(shù)即為答案。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 是樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)。

• 空間復(fù)雜度：O(n)，除去返回的答案需要的 O(n) 空間之外，我們還需要使用 O(h)（其中 h 是樹(shù)的高度）的空間存儲(chǔ)棧。這里 h < n，所以（在最壞情況下）總空間復(fù)雜度為 O(n)。

寫(xiě)在最后

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。