二叉树算法题实战：从遍历到子树判断

目次

一、弁言
二、判断两棵二叉树是否雷同
思绪
代码实现
注意点
三、二叉树的中序遍历
思绪
代码实现
注意点
四、判断一棵树是否为另一棵树的子树
思绪
代码实现
注意点
​编辑
五、增补

---

一、弁言

作者主页：共享家9527-CSDN博客
作者代码堆栈：
Study in the first semester of college.c: 大一放学期学习，紧张内容为个人学习过程记载
2025寒假C语言学习: 学习记载
   在算法学习和口试准备中，二叉树干系标题是常见且紧张的范例。本文将团结小米口试真题以及经典的二叉树算法题，分享解题思绪、代码实现以及一些必要注意的点。
  

二、判断两棵二叉树是否雷同


思绪


接纳递归的方式，从根节点开始比力。如果两个节点都为空，阐明它们雷同；如果此中一个为空，另一个不为空，则差别；如果两个节点值差别，也差别。然后递归地比力它们的左子树和右子树。

代码实现

2. c
4. bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
6.     if(p==NULL&&q==NULL) {
8.         return true;
10.     }
12.     if(p==NULL||q==NULL) {
14.         return false;
16.     }
18.     if(p->val!=q->val) {
20.         return false;
22.     }
24.     return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
26. }

复制代码

注意点


1. 递归停止条件的判断很关键，要先判断两个节点是否都为空，再判断单个节点为空的环境。

2. 比力节点值时，注意数据范例的划一性。

三、二叉树的中序遍历


思绪


中序遍历的序次是左子树、根节点、右子树。通过递归的方式，先遍历左子树，然后将根节点的值存入效果数组，末了遍历右子树。在实现时，必要盘算树的节点数，以便为效果数组分配空间。

代码实现


 

1. c
3. void midtree(struct TreeNode* root,int* arr,int* returnSize) {
5.     if(root==NULL) {
7.         return;
9.     }
11.     midtree(root->left,arr,returnSize);
13.     arr[(* returnSize)++]=root->val;
15.     midtree(root->right,arr,returnSize);
17. }
19. int treesize(struct TreeNode* root) {
21.     if(root==NULL) {
23.         return 0;
25.     }
27.     return treesize(root->left)+treexize(root->right)+1;
29. }
31. int* inorderTraversal(struct TreeNode* root, int* returnSize) {
33.     *returnSize=0;
35.     int n=treesize(root);
37.     int *arr=(int*)malloc(sizeof(int)*n);
39.     midtree(root,arr,returnSize);
41.     return arr;
43. }

复制代码

注意点


1. 递归函数中对数组和元素个数的利用要注意序次和边界。

2. 利用 malloc 分配内存后，调用者必要负责开释内存，制止内存走漏。

四、判断一棵树是否为另一棵树的子树


思绪


先判断当前两棵树是否雷同（利用前面的 isSameTree 函数），如果雷同则返回 true ；如果差别，则递归地在原树的左子树和右子树中继承查找是否存在与子树雷同的布局。

代码实现

2. c
4. bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
6.     // 同前面判断两棵树相同的代码
8. }
10. bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
12.     if(root==NULL) {
14.         return false;
16.     }
18.     if(isSameTree(root,subRoot)) {
20.         return true;
22.     }
24.     return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
26. }

复制代码

注意点


1. 递归调用时，要注意对空指针的处理惩罚，制止空指针非常。

2. 逻辑或 || 的利用，只要在左子树或右子树中找到匹配的子树即可。

五、增补


   1. 二叉树干系标题中，递归是常用的方法，但也可以利用栈等数据布局实现非递归版本，在时间和空间复杂度上大概会有所差别。
  
  2. 在口试中，除了写出正确的代码，还要可以或许清楚地论述解题思绪和时间、空间复杂度分析。
  
  通过对这些二叉树算法题的学习和实践，我们能更好地把握二叉树的布局和利用，为应对算法口试和现实开辟中的题目打下结实根本。