博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub算法专栏路漫漫其修远兮吾将上下而求索文章目录前言一、相同的树题目解读递归判断代码优化二、对称二叉树题目解读递归判断三、二叉树的前序遍历题目解读动态构建数组递归记录节点四、另一棵树的子树题目解读递归判断其他方法五、单值二叉树题目解读递归判断代码优化一行写法整活回归恢复更新前言本文章使用C语言进行题目讲解需读者掌握二叉树的相关基础知识适合刚手撕过二叉树代码或在刷算法题的读者。上一篇博客的总结中提到过“递归是二叉树的“母语 —— 几乎所有操作都可以用简洁的递归表达关键在于找准终止条件和递推关系。”这句话将在以下题目中得到验证实践是检验真理的唯一标准口牙。一、相同的树先看题目Go to…题目解读有两棵树 p q要求判断TA们的结构是否相同并且对应节点中的值是否一致最终返回 bool 值。我们用递归来解决这道题此题的判断能拆分成判断当前节点(根)判断左子树和判断右子树需注意当树的结构不同时直接判断根可能会因空指针访问导致报错。递归判断boolisSameTree(structTreeNode*p,structTreeNode*q){if(pNULLqNULL)returntrue;if(pNULL||qNULL)returnfalse;if(p-val!q-val)returnfalse;returnisSameTree(p-left,q-left)isSmaeTree(p-right,q-right);}在代码中判断当前的递归深度是否已经遍历到树的叶节点后并以此继续判断两棵树的结构是否相同如果相同则当 p 等于 NULL 时q 也等于 NULL不同时进入第二个 if 条件返回 false。做过了树的结构判断后剩下的问题就是根和左右子树了直接判断根并继续对应递归当前节点的左右子树。问为什么 true 或 false 会被正确的返回答最后的返回结构是 A B 的形式这意味着当一个结果返回 false 时最终因条件判断必定是 false而当全部结果都返回 true 时才是 true。代码优化boolisSameTree(structTreeNode*p,structTreeNode*q){if(!p||!q)#pNULL||qNULLreturnpq;returnp-valq-valisSameTree(p-left,q-left)isSameTree(p-right,q-right);}经思考能发现第一和第二条 if 能合并判断p 或 q 有一个为 NULL 时就进入并利用 p 是否等于 q 判断两颗树的结构是否相同作为返回值。最后将根和左右子树的判断合并为一行。二、对称二叉树先看题目Go to…题目解读检查一颗二叉树是否成镜像对称根相同左右子树互成镜像。与上一题相似能直接拆分成根和左右子树的问题互成镜像肯定也要求左右子树结构相同唯独节点值成镜像。递归判断boolisSameTree(structTreeNode*p,structTreeNode*q){if(!p||!q)returnpq;returnp-valq-valisSameTree(p-left,q-right)isSameTree(p-right,q-left);}boolisSymmetric(structTreeNode*root){if(!root)returntrue;returnisSameTree(root-left,root-right);}我们需判断这棵树的根是否为 NULL如果不为空就直接做CV工程师复用上一道题的方法确认这棵树的左右子树是否成镜像对称只需要修改遍历递出的方向让左孩子和右孩子判断右孩子和左孩子判断即可。三、二叉树的前序遍历先看题目Go to…题目解读此前序遍历非彼前序遍历不止要求前序遍历的方式还要将遍历的过程以数组的形式返回需额外再写一个函数用于遍历记录。动态构建数组voidPrevOrder(structTreeNode*root,int**nums,int*i){if(rootNULL)return;*numsrealloc(*nums,sizeof(int)*(*i1));(*nums)[(*i)]root-val;PrevOrder(root-left,nums,i);PrevOrder(root-right,nums,i);}int*preorderTraversal(structTreeNode*root,int*returnSize){int*numsNULL,i0;PrevOrder(root,nums,i);*returnSizei;returnnums;}创建一个指针用于开辟存储结果的动态空间并用下标 i 来记录下一个存储位置将树指针和 i 传入前序遍历函数注意 i 需使用地址传参使用值传参会导致 i 无法实际改变 i 的值当前节点不为 NULL 时数组开辟一个 int 大小的空间记录节点的值并让 i最后继续走前序的逻辑递归左右子树。递归记录节点intTreeSize(structTreeNode*root){if(rootNULL)return0;return1TreeSize(root-left)TreeSize(root-right);}voidPrevOrder(structTreeNode*root,int*nums,int*i){if(rootNULL)return;nums[(*i)]root-val;PrevOrder(root-left,nums,i);PrevOrder(root-right,nums,i);}int*preorderTraversal(structTreeNode*root,int*returnSize){int*numsNULL,i0;*returnSizeTreeSize(root);numsmalloc(sizeof(int)**returnSize);PrevOrder(root,nums,i);returnnums;}这种方式比上一种的简单一些不需要重复调整记录数组的大小。利用 TreeSize() 函数求二叉树的节点个数直接开辟对应个数的数组空间此时前序遍历函数只需将节点值放在数组中的对应位置即可。四、另一棵树的子树先看题目Go to…题目解读检查树 root 中是否包含子树 subRoot结构与值均一致包含返回 true否则返回 false。此题目可以复用 isSameTree() 函数暴力判断。递归判断boolisSameTree(structTreeNode*p,structTreeNode*q){if(!p||!q)returnpq;returnp-valq-valisSameTree(p-left,q-left)isSameTree(p-right,q-right);}boolisSubtree(structTreeNode*root,structTreeNode*subRoot){if(!root||!subRoot)returnrootsubRoot;returnisSameTree(root,subRoot)||isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);}递归 root 树并对每一个节点都使用 isSameTree() 函数与 subRoot 树做判断这相当于之前每个解法中的对根的操作随后继续递归左右子树即可暴力求解。其他方法暂时超出了博主的能力这一道题涵盖 KMP DFS HASH 和埃氏筛选法这些解法以后会在博客中补全。五、单值二叉树先看题目Go to…题目解读判断一棵二叉树所有节点中的值的是否一致一致被称为单值二叉树返回 true否则返回 false。此题继续拆分成根和左右子树的问题。递归判断boolPrevOrder(structTreeNode*root,intval){if(!root)returntrue;if(root-val!val)returnfalse;returnPrevOrder(root-left,val)PrevOrder(root-right,val);}boolisUnivalTree(structTreeNode*root){if(!root)returntrue;returnPrevOrder(root,root-val);}老生常谈的判断 root 是否为 NULL后使用前序遍历判断每个结点的值是否与根 root 的值相同最终所有值必须都相同所以使用 返回结果。代码优化boolisUnivalTree(structTreeNode*root){if(!root)returntrue;if(root-leftroot-val!root-left-val)returnfalse;if(root-rightroot-val!root-right-val)returnfalse;returnisUnivalTree(root-left)isUnivalTree(root-right);}使用根和左右子树的判断逻辑优化代码左孩子存在判断左孩子的值右孩子存在判断右孩子的值最后递归左右子树利用判断逻辑的传递性连接起整棵树的判断结果。一行写法整活boolisUnivalTree(structTreeNode*root){return!root||isUnivalTree(root-left)isUnivalTree(root-right)(!root-left||root-valroot-left-val)(!root-right||root-valroot-right-val);}此活需要读者对C语言表达式的短路语法有所了解也需要了解运算符的优先级和结合性。一行写法的判断逻辑沿用优化后的解答此活还有其它版本感兴趣的读者可以自行尝试。回归恢复更新好久不见前些时间我第一次参加了省里的一个比赛备赛花了一些时间再加上比赛后的一些事情直到现在才再次与读者相见。本次比赛有所遗憾没能取得最理想的成绩其原因在个人能力不足及比赛经验欠缺但对个人是一次宝贵的反馈(并且还有奖金虽然被学校收走一半就是了)。未来还会继续参加各种比赛没有说还会鸽很久的意思充实自己的能力并开始 GitHub 的使用和维护而在博客上也尽力写出更好的文章。⚛️EL PSY CONGROO十分感谢你的阅读过往博客《从线性表到单链表原理、实现与经典应用》已更新本期不确定下一篇博客先写排序算法还是OpenCode