LeetCode 二叉树 Swift 练习

发表于 更新于 分类于 阅读次数：

今天开始 LeetCode 二叉树。

Traverse A Tree

Binary Tree Preorder Traversal

144-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//
//  144-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/3.
//

// Binary Tree Preorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/928/
// https://leetcode.com/problems/binary-tree-preorder-traversal/

// 二叉树的前序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xeywh5/
// https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

// MARK: 递归

func preorderTraversal(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []

    preorderTraversalHelper(root, &result)

    return result
}

private func preorderTraversalHelper(_ root: TreeNode?, _ result: inout [Int]) {
    guard let root = root else {
        return
    }

    result.append(root.val)
    preorderTraversalHelper(root.left, &result)
    preorderTraversalHelper(root.right, &result)
}
144-c2.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//
//  144-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/3.
//

// Binary Tree Preorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/928/
// https://leetcode.com/problems/binary-tree-preorder-traversal/

// 二叉树的前序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xeywh5/
// https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

// MARK: 迭代

func preorderTraversal(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []
    var stack: [TreeNode] = []
    var node = root

    while !stack.isEmpty || node != nil {
        while node != nil {
            result.append(node!.val)
            stack.append(node!)
            node = node?.left
        }

        node = stack.removeLast()
        node = node?.right
    }

    return result
}
144-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//
//  144-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/3.
//

// Binary Tree Preorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/928/
// https://leetcode.com/problems/binary-tree-preorder-traversal/

// 二叉树的前序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xeywh5/
// https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

func preorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else {
        return []
    }

    var result: [Int] = []
    var stack: [Any] = [root]

    while !stack.isEmpty {
        let node = stack.removeLast()

        switch node {
        case let value as Int:
            result.append(value)
        case let node as TreeNode:
            if let rightNode = node.right {
                stack.append(rightNode)
            }

            if let leftNode = node.left {
                stack.append(leftNode)
            }

            stack.append(node.val)
        default:
            assertionFailure()
        }
    }

    return result
}

Binary Tree Inorder Traversal

94-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//
//  94-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/4.
//

// Binary Tree Inorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/929/
// https://leetcode.com/problems/binary-tree-inorder-traversal/

// 二叉树的中序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xecaj6/
// https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

// MARK: 递归

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []

    inorderTraversalHelper(root, &result)

    return result
}

private func inorderTraversalHelper(_ root: TreeNode?, _ result: inout [Int]) {
    guard let root = root else {
        return
    }

    inorderTraversalHelper(root.left, &result)
    result.append(root.val)
    inorderTraversalHelper(root.right, &result)
}
94-c2.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//
//  94-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/4.
//

// Binary Tree Inorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/929/
// https://leetcode.com/problems/binary-tree-inorder-traversal/

// 二叉树的中序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xecaj6/
// https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

// MARK: 迭代

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []
    var stack: [TreeNode] = []
    var node = root

    while !stack.isEmpty || node != nil {
        while node != nil {
            stack.append(node!)
            node = node?.left
        }

        node = stack.removeLast()
        result.append(node!.val)
        node = node?.right
    }

    return result
}
94-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//
//  94-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/4.
//

// Binary Tree Inorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/929/
// https://leetcode.com/problems/binary-tree-inorder-traversal/

// 二叉树的中序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xecaj6/
// https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

func inorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else {
        return []
    }

    var result: [Int] = []
    var stack: [Any] = [root]

    while !stack.isEmpty {
        let node = stack.removeLast()

        switch node {
        case let value as Int:
            result.append(value)
        case let node as TreeNode:
            if let rightNode = node.right {
                stack.append(rightNode)
            }

            stack.append(node.val)

            if let leftNode = node.left {
                stack.append(leftNode)
            }
        default:
            assertionFailure()
        }
    }

    return result
}

Binary Tree Postorder Traversal

145-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//
//  145-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/5.
//

// Binary Tree Postorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/930/
// https://leetcode.com/problems/binary-tree-postorder-traversal/

// 二叉树的后序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xebrb2/
// https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

// MARK: 递归

func postorderTraversal(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []

    postorderTraversalHelper(root, &result)

    return result
}

private func postorderTraversalHelper(_ root: TreeNode?, _ result: inout [Int]) {
    guard let root = root else {
        return
    }

    postorderTraversalHelper(root.left, &result)
    postorderTraversalHelper(root.right, &result)
    result.append(root.val)
}
145-c2.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//
//  145-c2.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/5.
//

// Binary Tree Postorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/930/
// https://leetcode.com/problems/binary-tree-postorder-traversal/

// 二叉树的后序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xebrb2/
// https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

// MARK: 迭代

func postorderTraversal(_ root: TreeNode?) -> [Int] {
    var result: [Int] = []
    var stack: [TreeNode] = []
    var node = root
    var prev: TreeNode?

    while !stack.isEmpty || node != nil {
        while node != nil {
            stack.append(node!)
            node = node?.left
        }

        node = stack.removeLast()

        if node?.right == nil || node?.right === prev {
            result.append(node!.val)
            prev = node
            node = nil
        } else {
            stack.append(node!)
            node = node?.right
        }
    }

    return result
}
145-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//
//  145-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2021/6/5.
//

// Binary Tree Postorder Traversal
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/930/
// https://leetcode.com/problems/binary-tree-postorder-traversal/

// 二叉树的后序遍历
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xebrb2/
// https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

func postorderTraversal2(_ root: TreeNode?) -> [Int] {
    guard let root = root else {
        return []
    }

    var result: [Int] = []
    var stack: [Any] = [root]

    while !stack.isEmpty {
        let node = stack.removeLast()

        switch node {
        case let value as Int:
            result.append(value)
        case let node as TreeNode:
            stack.append(node.val)

            if let rightNode = node.right {
                stack.append(rightNode)
            }

            if let leftNode = node.left {
                stack.append(leftNode)
            }
        default:
            assertionFailure()
        }
    }

    return result
}

Binary Tree Level Order Traversal

102-c1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//
//  102-c1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/15.
//  Updated by nuomi1 on 2021/6/6.
//

// Binary Tree Level Order Traversal
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/628/
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/931/
// https://leetcode.com/problems/binary-tree-level-order-traversal/

// 二叉树的层序遍历
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnldjj/
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/
// https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

// MARK: 广度优先搜索

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else {
        return []
    }

    var queue = [root]
    var result = [[Int]]()

    while !queue.isEmpty {
        var level = [Int]()
        let count = queue.count

        // 不能使用 queue.indices 因为 queue 被修改
        for _ in 0 ..< count {
            let node = queue.removeFirst()
            level.append(node.val)
            if let left = node.left {
                queue.append(left)
            }
            if let right = node.right {
                queue.append(right)
            }
        }

        result.append(level)
    }

    return result
}
102-s1.swiftview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//
//  102-s1.swift
//  LeetCode
//
//  Created by nuomi1 on 2019/1/15.
//  Updated by nuomi1 on 2021/6/6.
//

// Binary Tree Level Order Traversal
// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/628/
// https://leetcode.com/explore/learn/card/data-structure-tree/134/traverse-a-tree/931/
// https://leetcode.com/problems/binary-tree-level-order-traversal/

// 二叉树的层序遍历
// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnldjj/
// https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xefh1i/
// https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

func levelOrder(_ root: TreeNode?) -> [[Int]] {
    var result = [[Int]]()

    levelOrderHelper(root, 0, &result)

    return result
}

private func levelOrderHelper(_ root: TreeNode?, _ depth: Int, _ result: inout [[Int]]) {
    guard let root = root else {
        return
    }

    // 里层数组不存在时插入空数组
    if !result.indices.contains(depth) {
        result.insert([], at: depth)
    }

    result[depth].append(root.val)
    levelOrderHelper(root.left, depth + 1, &result)
    levelOrderHelper(root.right, depth + 1, &result)
}