📝 题目描述

题目链接：翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例：

示例 1：

1
2
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

1
2
输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

💡 解题思路

方法一：递归

深度优先搜索的思想，前序遍历和后序遍历的思想都可以解答这道题。

方法二：迭代

广度优先搜索，也就是层序遍历的思路。

访问每层的各个节点，然后交换其左右子树的指针。

🔧 代码实现

1、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTool(TreeNode* root) {
        if (!root) return nullptr;
        swap(root -> left, root -> right);
        invertTool(root -> left);
        invertTool(root -> right);
        return root;
    }
    TreeNode* invertTree(TreeNode* root) {
        return invertTool(root);
    }
};

2、迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        queue<TreeNode*> qu;
        qu.push(root);
        while(!qu.empty()) {
            TreeNode* tn = qu.front();
            qu.pop();
            // 交换左右子树
            swap(tn -> left, tn -> right);
            if (tn -> left) qu.push(tn -> left);
            if (tn -> right) qu.push(tn -> right);
        }
        return root;
    }
};

📊 复杂度分析

1、递归

  • 时间复杂度：O(N)O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。
  • 空间复杂度：O(N)O(N)，使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

2、迭代

  • 时间复杂度：O(N)O(N)，每个节点访问一次。
  • 空间复杂度：O(N)O(N)，取决于树的最大宽度。

🎯 总结

  • 核心思想：记住两种深度优先搜索和广度优先搜索方法。