LeetCode - #114 二叉樹展開為連結串列（Top 100）_Swift社群

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第30天，點選檢視活動詳情

前言

本題為 LeetCode 前 100 高頻題

我們社群陸續會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。）的 Swift 演算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 演算法到目前我們已經更新到 113 期，我們會保持更新時間和進度（週一、週三、週五早上 9:00 釋出），每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千里；不積小流，無以成江海，Swift社群伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水平：中等

1. 描述

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

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

2. 示例

示例 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

3. 答案

```swift / * 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 FlattenBinaryTreeLinkedList { func flatten(_ root: TreeNode?) { helper(root) }

private func helper(_ node: TreeNode?) -> TreeNode? {
    var node = node
    if node == nil {
        return node
    }
    if node!.left == nil && node!.right == nil {
        return node
    }

    let left = node!.left, right = node!.right
    node!.left = nil

    if let left = left {
        node!.right = left
        node = helper(left)
    }
    if let right = right {
        node!.right = right
        node = helper(right)
    }

    return node
}

} ```

主要思想：將 left 重置為 nil，並每次將當前節點更改為 left 子節點。
時間複雜度： O(n)
空間複雜度： O(1)

該演算法題解的倉庫：LeetCode-Swift

點選前往 LeetCode 練習

關於我們

我們是由 Swift 愛好者共同維護，我們會分享以 Swift 實戰、SwiftUI、Swift 基礎為核心的技術內容，也整理收集優秀的學習資料。