翻转二叉树

描述

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

让我们看一个示例：

编程练习

Kotlin

1internal object Solution {
2    fun invertTree(root: TreeNode): TreeNode {
3        return root
4    }
5}

解决方案

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

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

让我们回顾以下实现：

Kotlin

1internal object Solution {
2    fun invertTree(root: TreeNode?): TreeNode? {
3        if (root == null) {
4            return root
5        }
6        val right: TreeNode? = Solution.invertTree(root.right)
7        val left: TreeNode? = Solution.invertTree(root.left)
8        root.left = right
9        root.right = left
10        return root
11    }
12}
13
14fun main() {
15    val root = TreeNode(1)
16    root.left = TreeNode(2)
17    root.right = TreeNode(3)
18    root.left!!.left = TreeNode(4)
19    root.left!!.right = TreeNode(5)
20    root.right!!.left = TreeNode(6)
21    root.right!!.right = TreeNode(7)
22    Utility.print(Solution.invertTree(root))
23}

复杂度分析

时间复杂度

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

空间复杂度

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