翻转二叉树

描述

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

让我们看一个示例：

编程练习

Ruby

1require './TreeNode.rb'
2
3def invert_tree(root)
4
5end

解答

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

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

让我们回顾以下实现：

Ruby

1require './TreeNode.rb'
2
3def invert_tree(root) 
4    if root == nil  
5      return root
6    end
7    
8    right = invert_tree(root.right);
9    left = invert_tree(root.left);
10    root.left = right;
11    root.right = left;
12    return root;
13end
14
15
16# 驱动代码
17root = TreeNode.new(1)
18root.left = TreeNode.new(2)
19root.right = TreeNode.new(3)
20root.left.left = TreeNode.new(4)
21root.left.right = TreeNode.new(5)
22
23root.right.left = TreeNode.new(6)
24root.right.right = TreeNode.new(7)
25
26print_tree(invert_tree(root))

复杂度分析

时间复杂度

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

空间复杂度

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