二叉樹展開為鏈表（LeetCode 114）

題目鏈接：二叉樹展開為鏈表（LeetCode 114） 難度：中等

1. 題目描述

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

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

要求：

  • 節點數在範圍 [0, 2000] 內
  • -100 <= Node.val <= 100
  • 題目數據保證該樹為二叉樹（每個節點至多兩個子節點）

示例：

輸入: root = [1,2,5,3,4,null,6]
輸出: [1,null,2,null,3,null,4,null,5,null,6]
解釋: 展開後形成右指針鏈表：1 -> 2 -> 3 -> 4 -> 5 -> 6
輸入: root = []
輸出: []
輸入: root = [0]
輸出: [0]

2. 問題分析

2.1 規律

  • 二叉樹需要按前序遍歷（根-左-右）順序展開為單鏈表，使用 right 指針連接節點，left 始終為 null。
  • 類似於將樹結構轉換為線性結構，但需原地修改指針。
  • 核心問題：如何處理左子樹，使其插入到根和右子樹之間，同時保持前序順序？

2.2 O(1) 空間思路

我們使用迭代算法（類似於 Morris 遍歷的變體，實現 O(1) 空間）：

  • 不使用遞歸棧或額外數據結構，直接在樹上原地修改。
  • 遍歷根節點：
  • 如果存在左子樹，找到左子樹的最右節點（前驅節點）。
  • 將根的右子樹連接到這個最右節點的 right 上。
  • 然後將根的 right 設置為原左子樹，left 設置為 null。
  • 繼續向右移動（即新的 root.right）。
  • 這確保了前序順序：根 -> 左子樹全部 -> 右子樹全部，同時只用常數空間。
  • 基例：如果節點為空或無左子樹，直接向右移動。

3. 代碼實現

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        curr = root
        while curr:
            if curr.left:
                predecessor = curr.left
                while predecessor.right:
                    predecessor = predecessor.right
                predecessor.right = curr.right
                curr.right = curr.left
                curr.left = None
            curr = curr.right

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* curr = root;
        while (curr) {
            if (curr->left) {
                TreeNode* predecessor = curr->left;
                while (predecessor->right) {
                    predecessor = predecessor->right;
                }
                predecessor->right = curr->right;
                curr->right = curr->left;
                curr->left = nullptr;
            }
            curr = curr->right;
        }
    }
};

4. 複雜度分析

  • 時間複雜度：O(n)，每個節點被訪問常數次（遍歷和尋找前驅）。
  • 空間複雜度：O(1)，不使用額外空間，只用指針變量。

5. 總結

  • 樹結構轉換 + 前序順序 → 迭代 O(1) 空間是優化選擇
  • 核心利用左子樹最右節點連接右子樹，很通用
  • 類似 Morris 遍歷，但用於扁平化
  • 可擴展到其他樹扁平化變體

複習

面試經典150題[015]：分發糖果（LeetCode 135） 面試經典150題[045]：快樂數（LeetCode 202） 面試經典150題[060]：隨機鏈表的複製（LeetCode 138）