[特殊字符] LeetCode 100. 相同的树（C语言详解 | 递归 + 迭代）

题目描述给定两棵二叉树的根节点p和q判断它们是否完全相同。两棵树相同的条件结构相同对应节点值相同 解题思路这道题的本质是同时遍历两棵树逐节点比较我们可以采用递归DFS或迭代BFS✅ 方法一递归最优雅 思路拆解对于两个节点p和q1️⃣ 同时为空p NULL q NULL → true2️⃣ 一个为空p NULL || q NULL → false3️⃣ 值不同p-val ! q-val → false4️⃣ 递归判断左右子树left right C语言实现bool isSameTree(struct TreeNode* p, struct TreeNode* q) { // 都为空 if (p NULL q NULL) return true; // 一个为空 if (p NULL || q NULL) return false; // 值不同 if (p-val ! q-val) return false; // 递归左右子树 return isSameTree(p-left, q-left) isSameTree(p-right, q-right); } 图解理解核心思想p树 q树 1 1 / \ / \ 2 3 2 3 比较过程(1,1) ✔ ├── (2,2) ✔ └── (3,3) ✔只要有一个节点不一致 → 直接返回 false⏱ 复杂度分析类型复杂度时间复杂度O(n)空间复杂度O(h)递归栈✅ 方法二迭代队列 BFS 思路用两个队列同步遍历每次取出两个节点比较同时入队左右子节点 C语言实现#include stdlib.h bool isSameTree(struct TreeNode* p, struct TreeNode* q) { struct TreeNode* queue1[200]; struct TreeNode* queue2[200]; int front 0, rear 0; queue1[rear] p; queue2[rear] q; while (front rear) { struct TreeNode* n1 queue1[front]; struct TreeNode* n2 queue2[front]; if (n1 NULL n2 NULL) continue; if (n1 NULL || n2 NULL) return false; if (n1-val ! n2-val) return false; queue1[rear] n1-left; queue2[rear] n2-left; queue1[rear] n1-right; queue2[rear] n2-right; } return true; }⚠️ 易错点总结❌只比较值不比较结构// 错误写法缺少NULL判断 if (p-val q-val)❌忘记 NULL 情况// 会崩溃 p-val❌逻辑写错// 错误应该是 return left || right; 面试加分点 面试官常追问Q1为什么必须用因为左右子树必须同时相同Q2递归 vs 迭代方法优点缺点递归简洁直观栈空间迭代可控代码复杂Q3本质是什么 本质是树的结构 值的双重匹配问题 一句话总结“同步遍历 同时判断 全部匹配”