翻转二叉树

描述

在本节课中，你的任务是反转给定的二叉树 T。

让我们看一个示例：

Swift

1import Swift
2
3func invertTree(root: TreeNode?) -> TreeNode? {
4    return root
5}

解法

我们可以使用 深度优先搜索（DFS） 来解决这个问题。

空树的反转仍然是空树。要反转以 root 为根、左右子树分别为 left 和 right 的二叉树 T，我们保持 root 不变，仅反转其左右子树。

让我们回顾以下实现：

Swift

1import Swift
2
3func invertTree(root: TreeNode?) -> TreeNode? {
4    if root == nil {
5        return root
6    }
7    let right: TreeNode? = invertTree(root: root!.right)
8    let left: TreeNode? = invertTree(root: root!.left)
9    root!.left = right
10    root!.right = left
11    return root
12}
13
14func helper(node: TreeNode?, level: Int, levels: inout [[Int]]) {
15    // 开始当前层
16    if levels.count == level {
17        levels.append([])
18    }
19
20    // 填充当前层
21    levels[level].append(node!.val)
22
23    // 处理子节点以进入下一层
24    if node!.left != nil {
25        helper(node: node!.left, level: level + 1, levels: &levels)
26    }
27    if node!.right != nil {
28        helper(node: node!.right, level: level + 1, levels: &levels)
29    }
30}
31
32func to_string(vec: [[Int]]) -> String {
33    var str = "["
34    var i: Int = 0
35    var j: Int = 0
36    while i < vec.count {
37        str += "["
38        j = 0
39        while j < vec[i].count {
40            str += String(vec[i][j])
41            if j + 1 < vec[i].count {
42                str += ", "
43            }
44            j += 1
45        }
46        str += "]"
47        if i + 1 < vec.count {
48            str += ", "
49        }
50        i += 1
51    }
52    str += "]"
53    return str
54}
55
56func levelOrder(root: TreeNode?) -> [[Int]] {
57    var levels: [[Int]] = []
58    if root == nil { return levels }
59    helper(node: root, level: 0, levels: &levels)
60    return levels
61}
62
63func Print(root: TreeNode?) {
64    let vec: [[Int]] = levelOrder(root: root)
65    print(to_string(vec: vec))
66}
67
68let root: TreeNode = TreeNode(x: 1)
69root.left = TreeNode(x: 2)
70root.right = TreeNode(x: 3)
71root.left!.left = TreeNode(x: 4)
72root.left!.right = TreeNode(x: 5)
73
74root.right!.left = TreeNode(x: 6)
75root.right!.right = TreeNode(x: 7)
76
77let res: TreeNode? = invertTree(root: root)
78Print(root: root)

复杂度分析

时间复杂度

时间复杂度为 $O(n)$，其中 n 是树中节点的数量，因为我们需要访问每个节点一次。

空间复杂度

空间复杂度为 $O(n)$，其中 n 是树中节点的数量。在最坏情况下，树的高度等于 n（例如倾斜树），因此递归调用栈的最大深度为 n，导致空间复杂度为 $O(n)$。