二叉树经典题：从实现到优化渐进讲解（提供分析与图示）

前言

本文章使用C语言进行题目讲解，需读者掌握二叉树的相关基础知识，适合刚手撕过二叉树代码或在刷算法题的读者。
上一篇博客的总结中提到过：“递归是二叉树的“母语 —— 几乎所有操作都可以用简洁的递归表达，关键在于找准终止条件和递推关系。”
这句话将在以下题目中得到验证（实践是检验真理的唯一标准口牙）。

一、相同的树

先看题目：Go to…

题目解读

有两棵树 p q，要求判断TA们的结构是否相同，并且对应节点中的值是否一致，最终返回 bool 值。
我们用递归来解决这道题，此题的判断能拆分成判断当前节点(根)，判断左子树和判断右子树，需注意当树的结构不同时，直接判断根可能会因空指针访问导致报错。

递归判断

boolisSameTree(structTreeNode*p,structTreeNode*q){if(p==NULL&&q==NULL)returntrue;if(p==NULL||q==NULL)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)#p==NULL||q==NULLreturnp==q;returnp->val==q->val&&isSameTree(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)returnp==q;returnp->val==q->val&&isSameTree(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(root==NULL)return;*nums=realloc(*nums,sizeof(int)*(*i+1));(*nums)[(*i)++]=root->val;PrevOrder(root->left,nums,i);PrevOrder(root->right,nums,i);}int*preorderTraversal(structTreeNode*root,int*returnSize){int*nums=NULL,i=0;PrevOrder(root,&nums,&i);*returnSize=i;returnnums;}

创建一个指针用于开辟存储结果的动态空间，并用下标 i 来记录下一个存储位置，将树，指针和 i 传入前序遍历函数，注意 i 需使用地址传参，使用值传参会导致 i++ 无法实际改变 i 的值；当前节点不为 NULL 时，数组开辟一个 int 大小的空间记录节点的值并让 i++，最后继续走前序的逻辑，递归左右子树。

递归记录节点

intTreeSize(structTreeNode*root){if(root==NULL)return0;return1+TreeSize(root->left)+TreeSize(root->right);}voidPrevOrder(structTreeNode*root,int*nums,int*i){if(root==NULL)return;nums[(*i)++]=root->val;PrevOrder(root->left,nums,i);PrevOrder(root->right,nums,i);}int*preorderTraversal(structTreeNode*root,int*returnSize){int*nums=NULL,i=0;*returnSize=TreeSize(root);nums=malloc(sizeof(int)**returnSize);PrevOrder(root,nums,&i);returnnums;}

这种方式比上一种的简单一些，不需要重复调整记录数组的大小。
利用 TreeSize() 函数求二叉树的节点个数，直接开辟对应个数的数组空间，此时前序遍历函数只需将节点值放在数组中的对应位置即可。

四、另一棵树的子树

先看题目：Go to…

题目解读

检查树 root 中是否包含子树 subRoot，结构与值均一致，包含返回 true，否则返回 false。此题目可以复用 isSameTree() 函数暴力判断。

递归判断

boolisSameTree(structTreeNode*p,structTreeNode*q){if(!p||!q)returnp==q;returnp->val==q->val&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}boolisSubtree(structTreeNode*root,structTreeNode*subRoot){if(!root||!subRoot)returnroot==subRoot;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->left&&root->val!=root->left->val)returnfalse;if(root->right&&root->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->val==root->left->val)&&(!root->right||root->val==root->right->val);}

此活需要读者对C语言表达式的短路语法有所了解，也需要了解运算符的优先级和结合性。一行写法的判断逻辑沿用优化后的解答；此活还有其它版本，感兴趣的读者可以自行尝试。

回归！恢复更新

好久不见，前些时间我第一次参加了省里的一个比赛，备赛花了一些时间，再加上比赛后的一些事情，直到现在才再次与读者相见。本次比赛有所遗憾，没能取得最理想的成绩：

其原因在个人能力不足及比赛经验欠缺，但对个人，是一次宝贵的反馈(并且还有奖金，虽然被学校收走一半就是了)。未来还会继续参加各种比赛（没有说还会鸽很久的意思）充实自己的能力，并开始 GitHub 的使用和维护，而在博客上，也尽力写出更好的文章。

⚛️EL PSY CONGROO，十分感谢你的阅读
过往博客：《从线性表到单链表：原理、实现与经典应用》已更新

本期不确定：
下一篇博客先写排序算法还是OpenCode