【TomGo】二叉树递归一篇搞懂：从“会写”到“真正理解”（含全部代码+踩坑总结）

目录一、开头真实心路二、先说最核心递归三大模型 三、基础模块创建 销毁---1️⃣ 创建节点2️⃣ 销毁二叉树重点四、遍历递归入门---五、统计类加法模型六、查找类存在性七、树的高度max模型八、单值二叉树两种理解---九、结构类问题最核心---十、遍历扩展放入数组十一、最核心总结一定要记住十二、我这次真正学到的 ⚠️---一、开头真实心路大家好我是 TomGo 这段时间我把二叉树递归系统写了一遍但过程中有一个很明显的问题 ❗代码我能写出来但很多地方其实是“凭感觉写的”比如为什么销毁必须后序为什么有的地方用 有的用 ||为什么有的函数必须拆开写 这篇我把所有代码按模型彻底整理 把“为什么”讲清楚---二、先说最核心递归三大模型 我一开始是乱写的后来才发现 ❗所有二叉树递归本质就三种模型--- 1️⃣ 统计类加法模型结果 左子树 右子树 ( 当前节点)--- 2️⃣ 存在性||模型只要找到一个满足 → 就返回--- 3️⃣ 结构一致模型必须所有地方都满足--- 后面所有代码本质都在这三种里---三、基础模块创建 销毁---1️⃣ 创建节点BTNode* createNode(BTDataType x) { BTNode* newnode (BTNode*)malloc(sizeof(BTNode)); if (newnode NULL) { perror(malloc fail); exit(-1); } newnode-val x; newnode-left newnode-right NULL; return newnode; }---2️⃣ 销毁二叉树重点void freeTree(BTNode* root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); }---❌ 我踩过的坑我一开始以为这样就行free(root-left);free(root-right); 这是错的--- 为什么必须递归free 只释放一个节点不会帮你释放整棵子树--- 为什么必须“后序”必须先删子节点再删自己否则会访问野指针--- ❗总结一句话销毁 后序遍历---四、遍历递归入门---前序void PreOrder(BTNode* root) { if (root NULL) { printf( N ); return; } printf( %d , root-val); PreOrder(root-left); PreOrder(root-right); }---中序void InOrder(BTNode* root) { if (root NULL) { printf( N ); return; } InOrder(root-left); printf( %d , root-val); InOrder(root-right); }---后序void PostOrder(BTNode* root) { if (root NULL) { printf( N ); return; } PostOrder(root-left); PostOrder(root-right); printf( %d , root-val); }---五、统计类加法模型 这三题本质一样---节点个数本质就是 总数 左子树 右子树 1int BinaryTreeSize(BTNode* root) { return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1; }---叶子节点int BinaryTreeLeafSize(BTNode* root) { if (root NULL) return 0; if (root-left NULL root-right NULL) return 1; return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }这道题的递归过程其实可以这样理解递归会一直往下走直到走到最底层的叶子节点或者 NULL才停止。当遇到叶子节点时返回 1表示“找到一个叶子”。而对于非叶子节点它本身不是叶子它的任务只是 去左子树找叶子个数 去右子树找叶子个数最后把两边的结果加起来返回。所以整棵树的叶子个数本质就是左子树的叶子数 右子树的叶子数最终这个结果会一层一层向上返回直到回到根节点得到整棵树的叶子总数。这类问题的本质是当前节点不直接产生结果而是“汇总子树的结果”。这就是典型的“自底向上”的递归模型。第k层节点int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL || k 0) return 0; if (k 1) return 1; return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1); }--- 本质总结 ❗统计类 左 右 ( 当前)---六、查找类存在性BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) return NULL; if (root-val x) return root; BTNode* ret BinaryTreeFind(root-left, x); if (ret) return ret; return BinaryTreeFind(root-right, x); }这段代码的核心是先找左子树如果找到了就直接返回否则再去右子树找。具体过程是1️⃣ 先判断当前节点如果当前节点就是要找的值直接返回2️⃣ 如果不是就去左子树找如果左子树找到了ret 不为 NULL说明已经找到目标直接返回3️⃣ 如果左子树没找到ret 为 NULL才继续去右子树查找所以这里这个 if 很关键if (ret) return ret; 它的作用是一旦左子树找到了就“截断递归”避免继续往右子树查找--- 本质 ❗只要找到一个 → 返回|| 思想这段代码本质是“短路递归”左子树成功 → 直接返回左子树失败 → 才尝试右子树---七、树的高度max模型int TreeHeight(BTNode* root) { if (root NULL) return 0; int left TreeHeight(root-left); int right TreeHeight(root-right); return left right ? left 1 : right 1; }树的高度是一个“自底向上”的问题递归先计算子树高度当前节点只负责在子树结果基础上取最大值并加1我一开始以为是在“算整棵树”后来才明白每一层节点其实都只是在“接力”--- 本质高度 max(左,右) 1 注意这是“路径”不是“数量”---八、单值二叉树两种理解---❌ 写法1局部判断bool isUnivalTree(struct TreeNode* root){if (root NULL)return true;int n root-val;if (root-left root-left-val ! n)return false;if (root-right root-right-val ! n)return false;return isUnivalTree(root-left) isUnivalTree(root-right);} 但问题在于❗没有显式约束“所有节点都等于同一个值”而是靠“递归传递”去间接保证⚡ 为什么推荐写成 check(root, val)if (root-val ! val)return false; 这个是❗每个节点都直接和“统一标准”比较---✅ 写法2推荐全局判断bool check(struct TreeNode* root, int val) { if (root NULL) return true; if (root-val ! val) return false; return check(root-left, val) check(root-right, val); } bool isUnivalTree2(struct TreeNode* root) { if (root NULL) return true; return check(root, root-val); }--- 本质 ❗这是“全局一致性问题” → 用 ---九、结构类问题最核心---1️⃣ 完全相同的树isSamebool isSame(struct TreeNode* root1, struct TreeNode* root2) { if (root1 NULL root2 NULL) return true; if (root1 NULL || root2 NULL) return false; if (root1-val ! root2-val) return false; return isSame(root1-left, root2-left) isSame(root1-right, root2-right); }--- 本质 ❗必须全部一样 → 不是在“比较整棵树”而是每一对对应节点都在做“我和你一样吗”一层一层往下比只要有一个不一样 → 整体 false❌ 错误1合并判断TomGo的问题if (root1 NULL || root2 NULL || val不等) 会把NULL NULL应该 true判成 false ❌判断两棵树是否完全相同本质是递归比较对应节点如果当前节点相同并且左右子树分别完全相同则整棵树相同---2️⃣ 子树判断isContainsbool isContains(struct TreeNode* root1, struct TreeNode* root2) { if (root1 NULL) return false; if (isSame(root1, root2)) return true; return isContains(root1-left, root2) || isContains(root1-right, root2); }吧root1的所有节点都作为下一此递归的根来和root2进行IsSame验证--- 本质找位置 → ||匹配结构 → ---3️⃣ 对称二叉树bool IS(struct TreeNode* root1, struct TreeNode* root2) { if (root1 NULL root2 NULL) return true; if (root1 NULL || root2 NULL) return false; if (root1-val ! root2-val) return false; return IS(root1-left, root2-right) IS(root1-right, root2-left); }bool isSymmetric(struct TreeNode* root) 本质❗镜像左 ↔ 右十、遍历扩展放入数组void prevpush(struct TreeNode* root, int* a, int* pi) { if (root NULL) return; a[(*pi)] root-val; prevpush(root-left, a, pi); prevpush(root-right, a, pi); }因为i是输出型参数。想要改变就一定要传地址有小伙伴说前面加stack行吗但问题是多次调用之后i是之前所有调用的值的依次累加的结果这是十一、最核心总结一定要记住❗递归本质我只处理当前节点子树交给递归❗三大模型类型本质统计类左 右存在性结构一致❗关键区别 → 全部满足|| → 存在即可十二、我这次真正学到的 ⚠️我一开始以为我会递归其实只是“能写出来”当我能解释每一行代码为什么这样写的时候才算真正理解 面试会问什么为什么销毁必须后序为什么 isContains 用 ||为什么 isSame 用 为什么递归不能假设参数不为 NULL TomGo收尾递归不难难的是你以为你懂了