09、翻转二叉树

厨子大约 4 分钟数据结构算法算法基地面试递归二叉树刷题程序厨校招社招

哈喽，大家好，今天给大家介绍一道新题目，翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/description/open in new window

题目描述

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

示例 1:

输入: root = [4,2,7,1,3,6,9]
输出: [4,7,2,9,6,3,1]
翻转前：
        4
       / \
      2   7
     / \ / \
    1  3 6  9

翻转后：
        4
       / \
      7   2
     / \ / \
    9  6 3  1

每个节点的左右子树互换位置

示例 2:

输入: root = [2,1,3]
输出: [2,3,1]
翻转前：
    2
   / \
  1   3

翻转后：
    2
   / \
  3   1

示例 3:

输入: root = []
输出: []

约束条件:

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

翻转二叉树就是对每个节点，交换其左右子树。非常容易理解，就是将某个节点的左子树，变为其右子树，右子树变为其左子树

关键理解：

不是翻转节点的值，而是翻转子树的位置
每个节点的左右子节点互换
递归地对所有子树进行翻转

原始树：
        1
       / \
      2   3
     / \
    4   5

翻转过程（自底向上）:
━━━━━━━━━━━━━━━━━━━━
步骤1: 翻转节点2（叶子的父节点）
      2          2
     / \   →    / \
    4   5      5   4

步骤2: 翻转节点3（叶子节点，无需操作）
      3     →    3

步骤3: 翻转根节点1
        1              1
       / \            / \
      2   3    →     3   2
     / \                / \
    5   4              4   5

最终结果：
        1
       / \
      3   2
         / \
        4   5

上图的示例中，翻转是自下而上的哈，这个要注意

镜像对称的理解

翻转 = 镜像

原始树：               镜像树：
    1      │ 对称轴│     1
   / \     │      │    / \
  2   3    │      │   3   2
 /      \  │      │  /     \
4        5            5      4

就像照镜子一样，左右互换

常见误区

误区1: 只翻转根节点的左右子树
        1
       / \
      2   3
     / \
    4   5

错误: 只交换2和3，不递归翻转子树
结果:
        1
       / \
      3   2    ✗（节点2的子树4、5没有翻转）
         / \
        4   5

正确: 递归翻转所有子树
结果:
        1
       / \
      3   2
         / \
        5   4    ✓


误区2: 认为要改变节点的值
错误理解: 把节点值4和5互换
正确理解: 交换的是子树的指针，不是值


误区3: 认为只翻转叶子节点
        1
       / \
      2   3

错误: 只翻转最底层
正确: 每一层的每个节点都要翻转

可视化理解

示例: [1,2,3,4,5,6,7]

原始树（层序遍历）:
          1
        /   \
       2     3
      / \   / \
     4   5 6   7

翻转后（层序遍历）:
          1
        /   \
       3     2
      / \   / \
     7   6 5   4

对比：
第1层: 1 → 1（根节点不变）
第2层: 2,3 → 3,2（互换）
第3层: 4,5,6,7 → 7,6,5,4（对称翻转）

到这里基本就能够完全理解了，如果根据理解，无法写出代码的话，可以直接看题目代码进一步理解，然后再将题目代码默写出来

代码实现

递归（先交换再递归）⭐

/**
 * 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 == nullptr) {
            return nullptr;
        }

        // 交换当前节点的左右子树，这里要有一个临时节点接收哦
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        // 递归翻转左右子树
        invertTree(root->left);
        invertTree(root->right);

        // 返回根节点
        return root;
    }
};

时间复杂度: O(n)，n 是节点总数，每个节点访问一次

空间复杂度: O(h)，h 是树的高度（递归栈深度）

递归（先递归再交换）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        // 先递归翻转左右子树
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);

        // 再交换左右子树
        root->left = right;
        root->right = left;

        return root;
    }
};