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

一、题目描述给你一棵二叉树的根节点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; }⏱️ 七、复杂度分析方法时间复杂度空间复杂度递归O(n)O(h)迭代O(n)O(n)n节点数h树高 八、面试考点总结这题虽然简单但考察的是✅ 二叉树递归基本功✅ 指针操作C语言重点✅ DFS / BFS 思维转换 九、一句话总结翻转二叉树 每个节点左右子树交换 递归处理子树如果你在刷「面试经典 150 题」这题其实是二叉树递归模板题必须熟练到秒写