翻转二叉树

描述

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

让我们看一个示例：

编程练习

C#

1using System;
2using System.Collections.Generic;
3
4class Solution {
5    public static TreeNode invertTree(TreeNode root) {
6        // 请在此处编写你的代码
7        return root;
8    }
9}

解决方案

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

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

让我们回顾以下实现：

C#

1using System;
2using System.Collections.Generic;
3
4class Solution {
5    public static TreeNode invertTree(TreeNode root) {
6        if (root == null) {
7            return root;
8        }
9        TreeNode right = invertTree(root.right);
10        TreeNode left = invertTree(root.left);
11        root.left = right;
12        root.right = left;
13        return root;
14    }
15    public static void Main(){
16        TreeNode root = new TreeNode(1);
17        root.left = new TreeNode(2);
18        root.right = new TreeNode(3);
19        root.left.left = new TreeNode(4);
20        root.left.right = new TreeNode(5);
21
22        root.right.left = new TreeNode(6);
23        root.right.right = new TreeNode(7);
24        Utility.print(invertTree(root));
25    }
26}

复杂度分析

时间复杂度

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

空间复杂度

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