翻转二叉树

描述

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

让我们看一个示例如下：

Java

1class Solution {
2    public static TreeNode invertTree(TreeNode root) {
3        return root;
4    }
5}

解法

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

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

让我们回顾以下实现代码：

Java

1class Solution {
2    public static TreeNode invertTree(TreeNode root) {
3        if (root == null) {
4            return root;
5        }
6        TreeNode right = invertTree(root.right);
7        TreeNode left = invertTree(root.left);
8        root.left = right;
9        root.right = left;
10        return root;
11    }
12
13    public static void main(String args[]) {
14        TreeNode root = new TreeNode(1);
15        root.left = new TreeNode(2);
16        root.right = new TreeNode(3);
17        root.left.left = new TreeNode(4);
18        root.left.right = new TreeNode(5);
19
20        root.right.left = new TreeNode(6);
21        root.right.right = new TreeNode(7);
22        Utility.print(invertTree(root));
23    }
24}

复杂度分析

时间复杂度

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

空间复杂度

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