翻转二叉树

描述

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

让我们看一个示例：

编程练习

Go

1package main
2import (
3  "fmt"
4  "strconv"
5  "encoding/json"
6)
7
8type TreeNode struct{
9    val int
10    left *TreeNode
11    right *TreeNode
12}
13
14func invertTree(root *TreeNode) *TreeNode{
15    // 请在此处编写你的代码
16    return root
17}

解答

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

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

让我们回顾以下实现：

Go

1package main
2import (
3  "fmt"
4  "strconv"
5)
6
7type TreeNode struct{
8    val int
9    left *TreeNode
10    right *TreeNode
11}
12
13func invertTree(root *TreeNode) *TreeNode{
14    if root == nil {
15        return root
16    }
17
18    right := invertTree(root.right)
19    left := invertTree(root.left)
20    root.left = right
21    root.right = left
22    return root
23}
24
25func main() {
26    root := &TreeNode{val: 1}
27    root.left = &TreeNode{val: 2}
28    root.right = &TreeNode{val: 3}
29    root.left.left = &TreeNode{val: 4}
30    root.left.right = &TreeNode{val: 5}
31
32    root.right.left = &TreeNode{val: 6}
33    root.right.right = &TreeNode{val: 7}
34
35    print(invertTree(root))
36}

复杂度分析

时间复杂度

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

空间复杂度

空间复杂度为 $O(n)$，其中 n 是树中节点的数量。最坏情况下，树的高度等于 n（例如倾斜树），因此空间复杂度最高可达 $O(n)$。