当前位置：首页 > news >正文

[特殊字符] LeetCode 226. 翻转二叉树（C语言详解 | 递归 + 迭代）

news 2026/5/11 18:46:22

📌 一、题目描述

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

示例：

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

🧠 二、核心思路

这道题本质非常简单，可以总结为一句话：

对于每一个节点，交换它的左右子树。

也就是说：

当前节点：交换left和right
左子树：继续翻转
右子树：继续翻转

这天然符合递归结构（分治思想）

🔁 三、递归解法（推荐 ⭐）

✅ 解题步骤

递归终止：当前节点为空
交换左右子树
递归处理左右子树

💻 C语言代码

struct TreeNode* invertTree(struct TreeNode* root) { if (root == NULL) return NULL; // 交换左右子树 struct TreeNode* temp = root->left; root->left = root->right; root->right = temp; // 递归翻转左右子树 invertTree(root->left); invertTree(root->right); return root; }

🔍 四、递归过程图解

以示例[4,2,7,1,3,6,9]为例：

4 / \ 2 7 / \ / \ 1 3 6 9

第一步（根节点交换）：

4 / \ 7 2

然后递归处理：

节点 7 → 变成 9,6
节点 2 → 变成 3,1

最终结果：

4 / \ 7 2 / \ / \ 9 6 3 1

🔄 五、递归另一种写法（后序思想）

也可以先递归，再交换：

struct TreeNode* invertTree(struct TreeNode* root) { if (root == NULL) return NULL; struct TreeNode* left = invertTree(root->left); struct TreeNode* right = invertTree(root->right); root->left = right; root->right = left; return root; }

📌 区别：

第一种：前序交换
第二种：后序交换

👉 本质完全一样

🚀 六、迭代解法（BFS 层序遍历）

如果不使用递归，可以用队列实现：

💻 C语言代码

#include <stdlib.h> struct TreeNode* invertTree(struct TreeNode* root) { if (!root) return NULL; struct TreeNode* queue[100]; int front = 0, rear = 0; queue[rear++] = root; while (front < rear) { struct TreeNode* node = queue[front++]; // 交换左右子树 struct TreeNode* temp = node->left; node->left = node->right; node->right = temp; if (node->left) queue[rear++] = node->left; if (node->right) queue[rear++] = node->right; } return root; }