翻转二叉树

描述

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

让我们看一个示例：

编程练习

1defmodule Solution do
2  def invert_tree(_root) do
3    # 请在此处编写你的代码
4  end
5end

解答

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

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

让我们回顾以下实现：

1defmodule Trees do
2  def invert_tree(root) when root == nil, do: root
3  def invert_tree(root) do
4    right = invert_tree(root.right)
5    left = invert_tree(root.left)
6    %TreeNode{root | left: right, right: left}
7  end
8end
9
10# 驱动代码
11defmodule Main do
12  def main do
13    IO.puts "-----------------------------"
14    IO.puts "程序输出："
15
16    root = TreeNode.init(1)
17    root = %TreeNode{root | left: TreeNode.init(2)}
18    root = %TreeNode{root | right: TreeNode.init(3)}
19    root = %TreeNode{root | left: %TreeNode{root.left | left: TreeNode.init(4)}}
20    root = %TreeNode{root | left: %TreeNode{root.left | right: TreeNode.init(5)}}
21    root = %TreeNode{root | right: %TreeNode{root.right | left: TreeNode.init(6)}}
22    root = %TreeNode{root | right: %TreeNode{root.right | right: TreeNode.init(7)}}
23    Printing.print_tree(Trees.invert_tree(root))
24  end
25end

复杂度分析

时间复杂度

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

空间复杂度

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