Problem: 105. 從前序與中序遍歷序列構造二叉樹
給定兩個整數數組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。
【LeetCode 熱題 100】105. 從前序與中序遍歷序列構造二叉樹——（解法一）O（n^2）
文章目錄
- 整體思路
- 完整代碼
- 時空復雜度
- 時間復雜度：O(N)
- 空間復雜度：O(N)
整體思路
這段代碼同樣旨在解決 “從前序與中序遍歷序列構造二叉樹” 的問題。與上一個通過復制子數組的解法相比，此版本采用了哈希表和指針/索引來界定子數組范圍，從而極大地優化了時空效率，是解決此問題的標準最優解法。
算法的核心思想依然是基于前序和中序遍歷性質的分治法，但實現細節完全不同：
-
預處理：哈希表加速查找
- 算法首先創建一個哈希表
index，用于存儲中序遍歷中每個元素值及其對應的索引。 - 目的：這一步是性能優化的關鍵。它將“在中序遍歷中查找根節點位置”這個操作的時間復雜度從 O(N) 降到了 O(1)。
- 算法首先創建一個哈希表
-
通過索引定義子問題
- 算法不再通過
Arrays.copyOfRange來創建新的子數組，而是定義了一個輔助的dfs函數，它接收多個索引參數來界定當前需要處理的子數組范圍。 dfs(preorder, preL, preR, inL, inR, index):preL,preR: 定義了當前子樹在前序遍歷數組preorder中的范圍[preL, preR)(左閉右開)。inL,inR: 定義了當前子樹在中序遍歷數組inorder中的范圍[inL, inR)。
- 這種方式避免了任何數組復制，所有操作都在原始數組上進行。
- 算法不再通過
-
遞歸構造邏輯
dfs函數的執行流程如下：
a. 基線條件：if (preL == preR)，如果范圍為空，說明子樹為空，返回null。
b. 確定根節點：當前子樹的根節點值是preorder[preL]。
c. 分割子樹 (O(1) 操作)：- 使用預處理好的哈希表
index.get(preorder[preL])，瞬間（O(1)時間）找到根節點在中序遍歷中的位置，記為inRootIndex。 - 計算左子樹的大小
leftSize = inRootIndex - inL。
d. 遞歸構建左右子樹： - 左子樹：
* 前序范圍是[preL + 1, preL + 1 + leftSize)
* 中序范圍是[inL, inL + leftSize)
* 遞歸調用dfs(...)構建左子節點left。 - 右子樹：
* 前序范圍是[preL + 1 + leftSize, preR)
* 中序范圍是[inL + 1 + leftSize, inR)
* 遞歸調用dfs(...)構建右子節點right。
e. 合并結果：創建新的TreeNode，連接上一步構造出的left和right子節點，并返回。
- 使用預處理好的哈希表
通過哈希表和索引范圍，該算法將每一步遞歸中的核心操作都優化到了 O(1)，從而實現了整體的線性時間復雜度。
完整代碼
class Solution {/*** 根據前序遍歷和中序遍歷的結果，構造二叉樹（優化版）。* @param preorder 前序遍歷數組* @param inorder 中序遍歷數組* @return 構造出的二叉樹的根節點*/public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 步驟 1: 預處理，用哈希表存儲中序遍歷中值到索引的映射，以實現 O(1) 查找。Map<Integer, Integer> index = new HashMap<>(n);for (int i = 0; i < n; i++) {index.put(inorder[i], i);}// 調用輔助的 DFS 函數開始遞歸構建return dfs(preorder, 0, n, 0, n, index);}/*** 輔助 DFS 函數，通過索引范圍在原數組上構建子樹。* @param preorder 完整的前序遍歷數組* @param preL 當前子樹在前序數組中的左邊界（包含）* @param preR 當前子樹在前序數組中的右邊界（不包含）* @param inL 當前子樹在中序數組中的左邊界（包含）* @param inR 當前子樹在中序數組中的右邊界（不包含）* @param index 中序遍歷值到索引的映射哈希表* @return 構建好的子樹的根節點*/private TreeNode dfs(int[] preorder, int preL, int preR, int inL, int inR, Map<Integer, Integer> index) {// 遞歸的基線條件：如果范圍為空，則子樹為空。if (preL == preR) {return null;}// 根節點的值是前序遍歷范圍的第一個元素int rootVal = preorder[preL];// O(1) 時間從中序哈希表中獲取根節點的位置int inRootIndex = index.get(rootVal);// 計算左子樹的大小int leftSize = inRootIndex - inL;// 遞歸構建左子樹// 左子樹的前序范圍：[preL + 1, preL + 1 + leftSize)// 左子樹的中序范圍：[inL, inRootIndex) (即 inL + leftSize)TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftSize, inL, inRootIndex, index);// 遞歸構建右子樹// 右子樹的前序范圍：[preL + 1 + leftSize, preR)// 右子樹的中序范圍：[inRootIndex + 1, inR)TreeNode right = dfs(preorder, preL + 1 + leftSize, preR, inRootIndex + 1, inR, index);// 創建根節點，連接左右子樹，并返回return new TreeNode(rootVal, left, right);}
}
時空復雜度
時間復雜度：O(N)
- 哈希表預處理：
for循環遍歷inorder數組一次，構建哈希表。時間復雜度為 O(N)。 - 遞歸構建：
dfs函數會對preorder數組中的每個元素處理一次（作為一次根節點）。- 在
dfs函數內部，所有的操作——哈希表查找、算術運算、創建新節點——都是 O(1) 的。 - 由于每個節點只被訪問一次，總的遞歸構建時間為
N * O(1)= O(N)。
- 在
綜合分析：
總時間復雜度 = 預處理時間 + 遞歸構建時間 = O(N) + O(N) = O(N)。
空間復雜度：O(N)
- 哈希表：算法創建了一個哈希表
index來存儲中序遍歷的映射。在最壞情況下，所有元素都不同，哈希表需要存儲N個鍵值對。因此，哈希表占用的空間為 O(N)。 - 遞歸調用棧：遞歸的深度取決于樹的高度
H。- 在最好的情況下（一個完全二叉樹），
H約為log N，遞歸棧空間為 O(log N)。 - 在最壞的情況下（一個極度傾斜的鏈狀樹），
H等于N，遞歸棧空間為 O(N)。
- 在最好的情況下（一個完全二叉樹），
綜合分析：
算法所需的額外空間由哈希表和遞歸調用棧共同決定。總空間復雜度為 O(N) (哈希表) + O(H) (遞歸棧)。由于 H 的上界是 N，因此最壞情況下的總空間復雜度為 O(N) + O(N) = O(N)。
參考靈神
詳解)
