Problem: 114. 二叉樹展開為鏈表
給你二叉樹的根結點 root ，請你將它展開為一個單鏈表：
展開后的單鏈表應該同樣使用 TreeNode ，其中 right 子指針指向鏈表中下一個結點，而左子指針始終為 null 。
展開后的單鏈表應該與二叉樹 先序遍歷 順序相同。

【LeetCode 熱題 100】114. 二叉樹展開為鏈表——（解法一）后序遍歷+頭插法

整體思路

這段代碼同樣旨在解決 “二叉樹展開為鏈表” 的問題，即將二叉樹原地轉換成一個按前序遍歷順序串聯的“鏈表”。與上一個“后序遍歷+頭插法”的版本不同，此版本采用的是一種 “分解問題” (Divide and Conquer) 的思想，通過遞歸函數返回子問題（子樹）展開后的尾節點來輔助父問題的解決。

1. DFS函數的設計：

   • 該算法的核心是一個輔助函數 dfs(node)，它的設計目標是：
     a. 原地展開以 node 為根的子樹。
     b. 返回這棵子樹被展開成鏈表后的尾節點。

2. 分解與合并邏輯 (Divide and Conquer)：

   • 分解 (Divide)：對于當前節點 node，問題被分解為兩個子問題：展開左子樹和展開右子樹。這是通過遞歸調用 leftTail = dfs(node.left) 和 rightTail = dfs(node.right) 來實現的。
     • leftTail 會接收到左子樹展開后鏈表的尾節點。
     • rightTail 會接收到右子樹展開后鏈表的尾節點。
   • 解決 (Conquer)：當兩個子問題都解決后（即左右子樹都已各自拉平），開始處理當前節點 node，將其與兩個已拉平的子鏈表合并。
     • 合并的目標是形成 node -> (左子鏈表) -> (右子鏈表) 的結構。
     • if (leftTail != null): 這個判斷檢查是否存在左子樹。
       • leftTail.right = node.right;: 這是最關鍵的一步。它將左子鏈表的尾部 (leftTail) 的 right 指針，連接到原先 node 的右子樹（現在已經是右子鏈表的頭部）。這就把左右兩個鏈表串起來了。
       • node.right = node.left;: 將 node 的右指針指向其左孩子，即左子鏈表的頭部。
       • node.left = null;: 將 node 的左指針置空。
     • 完成這三步后，以 node 為根的子樹已經被成功展開。

3. 返回尾節點：

   • 在合并完成后，需要確定并返回當前整個大鏈表（node + 左子鏈表 + 右子鏈表）的尾節點。
   • 這個尾節點的位置有三種可能：
     a. 如果存在右子樹，那么尾節點就是右子樹的尾節點 (rightTail)。
     b. 如果不存在右子樹但存在左子樹，那么尾節點就是左子樹的尾節點 (leftTail)。
     c. 如果左右子樹都不存在，那么尾節點就是 node 本身。
   • return rightTail != null ? rightTail : leftTail != null ? leftTail : node; 這句三元表達式完美地實現了這個邏輯。

這個算法通過自底向上的方式，在每一層都完成子樹的展開和連接，最終將整個樹拉平。

完整代碼

class Solution {/*** 將給定的二叉樹原地展開為鏈表。* @param root 二叉樹的根節點*/public void flatten(TreeNode root) {// 調用輔助的DFS函數，主函數不需要返回值dfs(root);}/*** 輔助DFS函數：原地展開以 node 為根的子樹，并返回展開后鏈表的尾節點。* @param node 當前子樹的根節點* @return 展開后鏈表的尾節點*/private TreeNode dfs(TreeNode node) {// 基線條件：如果節點為空，則沒有什么可展開的，返回 null。if (node == null) {return null;}// 1. 分解：遞歸地展開左右子樹，并獲取它們展開后的尾節點。TreeNode leftTail = dfs(node.left);   // 展開左子樹，獲取左鏈表的尾TreeNode rightTail = dfs(node.right); // 展開右子樹，獲取右鏈表的尾// 2. 解決/合并：處理當前節點 node，將其與已展開的左右子鏈表連接。// 如果存在左子樹（即左子鏈表），才需要進行連接操作。if (leftTail != null) {// a. 將左鏈表的尾部的 right 指針，指向右子鏈表的頭部 (node.right)。leftTail.right = node.right;// b. 將 node 的右指針指向左子鏈表的頭部 (node.left)。node.right = node.left;// c. 將 node 的左指針置空。node.left = null;}// 3. 返回當前已展開大鏈表的尾節點。// 優先級：右子樹的尾 > 左子樹的尾 > 當前節點本身。if (rightTail != null) {return rightTail;}if (leftTail != null) {return leftTail;}return node;}
}

時空復雜度

時間復雜度：O(N)

1. 節點訪問：該算法通過DFS遞歸遍歷了樹中的每一個節點。每個節點被訪問和處理一次。
2. 操作：在每個節點上，執行的都是常數時間的指針操作。
3. 綜合分析：
   • 如果樹中有 N 個節點，dfs 函數會被調用 N 次。
   • 因此，總的時間復雜度與節點數成正比，即 O(N)。

空間復雜度：O(H)

1. 主要存儲開銷：算法是原地修改，沒有創建新的數據結構來存儲節點。主要的額外空間開銷來自于 遞歸調用棧。
2. 空間大小：遞歸調用的深度取決于樹的高度 H。
   • 在最好的情況下（一個完全二叉樹），樹的高度 H 約為 log N，空間復雜度為 O(log N)。
   • 在最壞的情況下（一個極度傾斜的鏈狀樹），樹的高度 H 等于 N，此時遞歸棧的深度也為 N，空間復雜度為 O(N)。

綜合分析：
算法的輔助空間復雜度主要由遞歸棧的深度決定，即樹的高度 H。因此，空間復雜度為 O(H)。在最壞情況下，H 可能為 N，所以最壞空間復雜度也可以表述為 O(N)。

參考靈神