翻转二叉树

描述

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

让我们看一个示例：

编程练习

JS

1import {TreeNode} from './TreeNode.js'
2
3function invertTree(root){
4  
5}

解答

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

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

下面回顾一下实现代码：

JS

1function invertTree(root){
2    if (root == null)
3      return root
4
5    var right = invertTree(root.right)
6    var left = invertTree(root.left)
7    root.left = right
8    root.right = left
9    return root
10}
11
12// 驱动代码
13var root = new TreeNode(1)
14root.left = new TreeNode(2)
15root.right = new TreeNode(3)
16root.left.left = new TreeNode(4)
17root.left.right = new TreeNode(5)
18
19root.right.left = new TreeNode(6)
20root.right.right = new TreeNode(7)
21
22printTree(invertTree(root))

复杂度分析

时间复杂度

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

空间复杂度

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