翻转二叉树

描述

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

让我们看一个示例：

Scala

1class TreeNode(var value: Int = 0, var left: TreeNode = null, var right: TreeNode = null) {
2}
3
4object Solution {
5  def invertTree(root: TreeNode): TreeNode = {
6    // 请在此处编写你的代码
7    root
8  }
9}

解法

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

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

让我们回顾以下实现：

Scala

1import scala.collection.mutable.ListBuffer
2
3object Main {
4  class TreeNode(var value: Int = 0, var left: TreeNode = null, var right: TreeNode = null) {
5  }
6
7  class Utility {
8    def helper(node: TreeNode, level: Int, levels: ListBuffer[ListBuffer[Int]]): Unit = {
9      // 开始当前层
10      if (levels.size == level)
11        levels.addOne(new ListBuffer[Int])
12      // 填充当前层
13      levels(level).addOne(node.value)
14      // 处理子节点以进入下一层
15      if (node.left != null)
16        helper(node.left, level + 1, levels)
17      if (node.right != null)
18        helper(node.right, level + 1, levels)
19    }
20
21    def levelOrder(root: TreeNode): ListBuffer[ListBuffer[Int]] = {
22      val levels = new ListBuffer[ListBuffer[Int]]
23      if (root == null)
24        return levels
25      helper(root, 0, levels)
26      levels
27    }
28
29    def print(root: TreeNode): Unit = {
30      println(levelOrder(root))
31    }
32  }
33
34  def invertTree(root: TreeNode): TreeNode = {
35    if (root == null) return root
36    val right = invertTree(root.right)
37    val left = invertTree(root.left)
38    root.left = right
39    root.right = left
40    root
41  }
42
43  def main(args: Array[String]): Unit = {
44    val root = new TreeNode(1)
45    root.left = new TreeNode(2)
46    root.right = new TreeNode(3)
47    root.left.left = new TreeNode(4)
48    root.left.right = new TreeNode(5)
49    root.right.left = new TreeNode(6)
50    root.right.right = new TreeNode(7)
51    new Utility().print(invertTree(root))
52  }
53}

复杂度分析

时间复杂度

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

空间复杂度

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