翻转二叉树

描述

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

让我们看一个示例：

编程练习

Python

1from TreeNode import *
2def invert_tree(root):
3  pass

解答

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

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

让我们回顾以下实现：

Python

1from TreeNode import *
2def invert_tree(root):
3    if root is None: 
4      return root
5
6    right = invert_tree(root.right);
7    left = invert_tree(root.left);
8    root.left = right;
9    root.right = left;
10    return root;
11
12# 测试代码
13root = TreeNode(1)
14root.left = TreeNode(2)
15root.right = TreeNode(3)
16root.left.left = TreeNode(4)
17root.left.right = TreeNode(5)
18
19root.right.left = TreeNode(6)
20root.right.right = TreeNode(7)
21
22print_tree(invert_tree(root))

复杂度分析

时间复杂度

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

空间复杂度

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