更新時間：2025-04-04

• 算法題解目錄匯總：算法刷題記錄——題解目錄匯總
• 技術博客總目錄：計算機技術系列博客——目錄頁

優先整理熱門100及面試150，不定期持續更新，歡迎關注！

---

114. 二叉樹展開為鏈表

給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：

展開后的單鏈表應該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結點，而左子指針始終為 null 。
展開后的單鏈表應該與二叉樹 先序遍歷 順序相同。

示例 1：

輸入：root = [1,2,5,3,4,null,6]
輸出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

輸入：root = []
輸出：[]

示例 3：

輸入：root = [0]
輸出：[0]

提示：

• 樹中結點數在范圍 [0, 2000] 內
• -100 <= Node.val <= 100

進階：
你可以使用原地算法（O(1) 額外空間）展開這棵樹嗎？

方法一：迭代先序遍歷（顯式棧）

利用棧模擬先序遍歷，維護前驅節點prev，實時修改指針建立鏈表。

• 核心思想：利用棧按「根→右→左」順序壓入節點，確保彈出順序為「根→左→右」。
• 指針調整：維護前驅節點prev，每次將prev的right指向當前節點，并清空left指針。
• 空間優化：棧的深度為樹高，平均空間復雜度為O(log n)。

代碼實現(Java)：

public class Solution {public void flatten(TreeNode root) {if (root == null) return;Stack<TreeNode> stack = new Stack<>();stack.push(root);TreeNode prev = null;while (!stack.isEmpty()) {TreeNode current = stack.pop();// 將前驅節點的right指向當前節點，left置空if (prev != null) {prev.right = current;prev.left = null;}prev = current;// 先壓入右子節點，再壓入左子節點（棧的LIFO特性）if (current.right != null) stack.push(current.right);if (current.left != null) stack.push(current.left);}}
}

方法二：遞歸后序遍歷（連接左右子樹）

遞歸處理左右子樹，將左子樹連接到右子樹之前，并更新末尾節點。

• 核心思想：將左子樹末尾連接到右子樹頭部，再讓根節點指向左子樹。
• 末尾處理：返回展開后的最后一個節點，避免每次遍歷鏈表末尾，時間復雜度優化至O(n)。
• 邏輯簡化：通過后序遍歷自底向上處理，確保左子樹完全展開后再處理根節點。

代碼實現(Java)：

public class Solution {public void flatten(TreeNode root) {flattenHelper(root);}private TreeNode flattenHelper(TreeNode node) {if (node == null) return null;// 遞歸處理左右子樹，獲取展開后的末尾節點TreeNode leftTail = flattenHelper(node.left);TreeNode rightTail = flattenHelper(node.right);// 將左子樹插入到當前節點與右子樹之間if (node.left != null) {leftTail.right = node.right;node.right = node.left;node.left = null;}// 返回當前子樹展開后的最后一個節點return (rightTail != null) ? rightTail : (leftTail != null) ? leftTail : node;}
}

復雜度分析

• 時間復雜度：兩種方法均為 O(n)，每個節點被訪問一次。
• 空間復雜度：
  • 迭代法：O(h)，h為樹高，最壞情況（鏈表結構）為O(n)。
  • 遞歸法：O(h)，遞歸棧深度為樹高。

對比總結

• 迭代法：適合大規模數據或樹結構較深時，避免遞歸棧溢出。
• 遞歸法：代碼簡潔，適合對代碼可讀性要求高，且無棧溢出風險的場景。

---

聲明

1. 本文版權歸 CSDN 用戶 Allen Wurlitzer 所有，遵循CC-BY-SA協議發布，轉載請注明出處。
2. 本文題目來源 力扣-LeetCode ，著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。