文章目錄
-
-
-
- 一、給定前序和中序周遊，重構二叉樹
- 二、給定中序和後續周遊，重構二叉樹
-
-
一、給定前序和中序周遊，重構二叉樹
leetcode 105号題
題目： 根據一棵二叉樹的前序和中序周遊，重構出這棵樹。樹中沒有重複元素
例如，給出：
前序周遊 preorder = [3,9,20,15,7]
中序周遊 inorder = [9,3,15,20,7]
傳回如下二叉樹：
3
/ \
9 20
/ \
15 7
題解：
- 前序周遊是根左右的順序，中序周遊是左根右的順序；
- 前序周遊的第一個元素必然是整棵樹的根節點，知道根節點之後我們就可以依據中序周遊切分出左右子樹；
- 我們在中序序列中分割好了左右子樹之後，我們再找到左右子樹在前序周遊和中序周遊中的起始位置，這樣就可以把我們找到的左右子樹再作為一棵單獨的樹來進行處理；
- 重複2,3兩個步驟
整體的思想就是這樣的，現在來看具體怎麼做：
首先定義如下幾個變量：
- iStart（中序的起始位置下标）
- iEnd（中序的結束位置下标）
- pStart（前序的起始位置下标）
- pEnd（前序的結束位置下标）
- rIndex（根節點在中序中的下标）
先看一下這幾個變量是怎麼變化的：
紅色：根節點
綠色：左子樹
藍色：右子樹
根據圖中的标注，可以得到下面這些資訊：
1. 左子樹的長度：rIndex-iStart
2. 右子樹的長度：iEnd-rIndex +1
左子樹在前序周遊中的開始位置：pStart + 1
左子樹在前序周遊中的結束位置：pStart + rIndex - iStart
左子樹在中序周遊中的開始位置：iStart
左子樹在中序周遊中的結束位置：rIndex- 1
右子樹在前序周遊中的開始位置：pStart + 1 + rIndex - iStart
右子樹在前序周遊中的結束位置：pEnd
右子樹在中序周遊中的開始位置：rIndex + 1
右子樹在中序周遊中的結束位置：iEnd
代碼實作：
class Solution {
// map存儲中序中節點值與下标的映射關系，友善擷取根節點在中序中的下标
public HashMap<Integer,Integer> map = new HashMap<>();
public TreeNode buildTree(int [] pre,int [] in) {
for (int i = 0; i <= in.length - 1; i++) {
map.put(in[i],i);
}
return dfs(pre, 0, pre.length - 1, 0, in.length - 1);
}
public TreeNode dfs(int[] preOrder, int pStart, int pEnd, int iStart, int iEnd) {
if (pStart > pEnd) {
return null;
}
TreeNode node = new TreeNode(preOrder[pStart]);
int rIndex = map.get(node.val);
TreeNode left = dfs(preOrder, pStart + 1, pStart + rIndex - iStart, iStart, rIndex - 1);
TreeNode right = dfs(preOrder, pStart + 1 + rIndex - iStart, pEnd, rIndex + 1, iStart);
node.left = left;
node.right = right;
return node;
}
}
二、給定中序和後續周遊，重構二叉樹
leetcode 106号題
題目： 根據一棵二叉樹的中序和後序周遊，重構出這棵樹。樹中沒有重複元素
例如，給出
中序周遊 inorder = [9,3,15,20,7]
後序周遊 postorder = [9,15,7,20,3]
傳回如下的二叉樹：
3
/ \
9 20
/ \
15 7
題解：
這個題和上一題其實是一樣的思路：
- 後序周遊是根左右的順序，中序周遊是左根右的順序；
- 後序周遊的最後一個元素必然是整棵樹的根節點，知道根節點之後我們就可以依據中序周遊切分出左右子樹；
- 我們在中序序列中分割好了左右子樹之後，我們再找到左右子樹在後序周遊和中序周遊中的起始位置，這樣就可以把我們找到的左右子樹再作為一棵單獨的樹來進行處理；
- 重複2,3兩個步驟
還是定義幾個變量：
- iStart（中序的起始位置下标）
- iEnd（中序的結束位置下标）
- pStart（後序的起始位置下标）
- pEnd（後序的結束位置下标）
- rIndex（根節點在中序中的下标）
還是和上面一樣，我們先看一下這幾個值的變化：
根據圖中的标注，我們也可以得出以下資訊：
1. 左子樹的長度：rIndex-iStart
2. 右子樹的長度：iEnd-rIndex +1
左子樹在後序周遊中的開始位置：pStart
左子樹在後序周遊中的結束位置：pStart + rIndex-iStart - 1
左子樹在中序周遊中的開始位置：iStart
左子樹在中序周遊中的結束位置：rIndex- 1
右子樹在後序周遊中的開始位置：pStart+ rIndex - iStart
右子樹在後序周遊中的結束位置：pEnd - 1
右子樹在中序周遊中的開始位置：rIndex + 1
右子樹在中序周遊中的結束位置：iEnd
代碼實作：
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return help(postorder, 0, inorder.length - 1, 0, postorder.length - 1);
}
public TreeNode help(int[] post, int iStart, int iEnd, int pStart, int pEnd) {
if (pStart > pEnd) return null;
int rootVal = post[pEnd];
int rIndex = map.get(rootVal);
TreeNode node = new TreeNode(rootVal);
node.left = help(post, iStart, rIndex - 1, pStart, pStart + rIndex - iStart - 1);
node.right = help(post, rIndex + 1, iEnd, pStart + rIndex - iStart , pEnd - 1);
return node;
}
}
這兩道題的思路幾乎是一緻的，主要是要想明白前序和中序、中序和後序有什麼關聯。找到它們之間的關系，這兩個題就解決了。
期待大家批評指正