一、題目描述
根據一棵樹的中序周遊與後序周遊構造二叉樹。
注意:
你可以假設樹中沒有重複的元素。
例如，給出
中序周遊 inorder = [9,3,15,20,7]
後序周遊 postorder = [9,15,7,20,3]
傳回如下的二叉樹：
二、思路
思路來源于圖解構造二叉樹之中序+後序，畫得圖是真心棒
前提
解決此問題的關鍵在于要很熟悉樹的各種周遊次序代表的什麼，最好能夠将圖畫出來。本題解帶你先進行中序周遊和後續周遊二叉樹，然後再根據周遊結果将二叉樹進行還原。
首先，來一棵樹
然後再看樹的周遊結果
根據中序和後序周遊結果還原二叉樹
中序周遊和後續周遊的特性
首先來看題目給出的兩個已知條件中序周遊序列和後序周遊序列 根據這兩種周遊的特性我們可以得出兩個結論
- 在後序周遊序列中,最後一個元素為樹的根節點
- 在中序周遊序列中,根節點的左邊為左子樹，根節點的右邊為右子樹
如下圖所示
樹的還原過程描述
根據中序周遊和後續周遊的特性我們進行樹的還原過程分析
- 首先在後序周遊序列中找到根節點(最後一個元素)
- 根據根節點在中序周遊序列中找到根節點的位置
- 根據根節點的位置将中序周遊序列分為左子樹和右子樹
- 根據根節點的位置确定左子樹和右子樹在中序數組和後續數組中的左右邊界位置
- 遞歸構造左子樹和右子樹
- 傳回根節點結束
樹的還原過程變量定義
需要定義幾個變量幫助我們進行樹的還原
- HashMap memo 需要一個哈希表來儲存中序周遊序列中,元素和索引的位置關系.因為從後序序列中拿到根節點後，要在中序序列中查找對應的位置,進而将數組分為左子樹和右子樹
- int ri 根節點在中序周遊數組中的索引位置
- 中序周遊數組的兩個位置标記 [is, ie],is是起始位置，ie是結束位置
- 後序周遊數組的兩個位置标記 [ps, pe] ps是起始位置，pe是結束位置
位置關系的計算
在找到根節點位置以後，我們要确定下一輪中，左子樹和右子樹在中序數組和後續數組中的左右邊界的位置。
- 左子樹-中序數組 is = is, ie = ri - 1
- 左子樹-後序數組 ps = ps, pe = ps + ri - is - 1 (pe計算過程解釋，後續數組的起始位置加上左子樹長度-1 就是後後序數組結束位置了，左子樹的長度 = 根節點索引-左子樹)
- 右子樹-中序數組 is = ri + 1, ie = ie
- 右子樹-後序數組 ps = ps + ri - is, pe - 1
聽不明白沒關系，看圖就對了,計算圖示如下
樹的還原過程
三、代碼實作
修改了原作者對變量的命名，現在國小二年級的弟弟都看懂了。
将中序周遊和後序周遊的數組抽離到類成員級别，可以有效的避免數組在多次遞歸中的複制操作，提升運作效率。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
//儲存中序周遊數值與下标的映射關系
Map<Integer, Integer> inOrderMap = new HashMap<>();
//後序周遊數組
int[] postOrderArray;
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++) {
inOrderMap.put(inorder[i], i);
}
postOrderArray = postorder;
return build(0, inorder.length - 1, 0, postorder.length - 1);
}
/**
* @param inOrderStart 中序周遊下标開始值
* @param inOrderEnd 中序周遊下标結束值
* @param postOrderStart 後序周遊下标開始值
* @param postOrderEnd 後序周遊下标結束值
* @return
*/
public TreeNode build(int inOrderStart, int inOrderEnd, int postOrderStart, int postOrderEnd) {
if (inOrderStart > inOrderEnd || postOrderStart > postOrderEnd) {
return null;
}
//擷取根節點
int rootValue = postOrderArray[postOrderEnd];
//根節點在中序周遊中的索引
int rootIndex = inOrderMap.get(rootValue);
//構造根節點
TreeNode root = new TreeNode(rootValue);
root.left = build(inOrderStart, rootIndex - 1, postOrderStart, postOrderStart + rootIndex - inOrderStart - 1);
root.right = build(rootIndex + 1, inOrderEnd, postOrderStart + rootIndex - inOrderStart, postOrderEnd - 1);
return root;
} 該方案需要通路長度為n的map與數組，且節點總數目也為n，是以時間複雜度為O(n)