翻转二叉树

描述

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

让我们看一个示例：

编程练习

C++

1#include "TreeNode.h"
2TreeNode* invertTree(TreeNode* root) {
3    return root;
4}

解答

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

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

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

C++

1TreeNode* invertTree(TreeNode* root) {
2    if (root == nullptr) {
3        return root;
4    }
5    TreeNode* right = invertTree(root->right);
6    TreeNode* left = invertTree(root->left);
7    root->left = right;
8    root->right = left;
9    return root;
10}
11
12int main(){
13    TreeNode* root = new TreeNode(1);
14    root->left = new TreeNode(2);
15    root->right = new TreeNode(3);
16    root->left->left = new TreeNode(4);
17    root->left->right = new TreeNode(5);
18
19    root->right->left = new TreeNode(6);
20    root->right->right = new TreeNode(7);
21
22    auto res = invertTree(root);
23    print(root);
24    return 0;
25}

复杂度分析

时间复杂度

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

空间复杂度

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