目录
一、引言
作者主页：共享家9527-CSDN博客
作者代码仓库：
Study in the first semester of college.c: 大一下学期学习，主要内容为个人学习过程记录
在算法学习和面试准备中，二叉树相关题目是常见且重要的类型。本文将结合小米面试真题以及经典的二叉树算法题，分享解题思路、代码实现以及一些需要注意的点。
二、判断两棵二叉树是否相同
思路
采用递归的方式，从根节点开始比较。如果两个节点都为空，说明它们相同；如果其中一个为空，另一个不为空，则不同；如果两个节点值不同，也不同。然后递归地比较它们的左子树和右子树。
代码实现
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);
}
注意点
1. 递归终止条件的判断很关键，要先判断两个节点是否都为空，再判断单个节点为空的情况。
2. 比较节点值时，注意数据类型的一致性。
三、二叉树的中序遍历
思路
中序遍历的顺序是左子树、根节点、右子树。通过递归的方式，先遍历左子树，然后将根节点的值存入结果数组，最后遍历右子树。在实现时，需要计算树的节点数，以便为结果数组分配空间。
代码实现
c
void midtree(struct TreeNode* root,int* arr,int* returnSize) {
if(root==NULL) {
return;
}
midtree(root->left,arr,returnSize);
arr[(* returnSize)++]=root->val;
midtree(root->right,arr,returnSize);
}
int treesize(struct TreeNode* root) {
if(root==NULL) {
return 0;
}
return treesize(root->left)+treexize(root->right)+1;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize=0;
int n=treesize(root);
int *arr=(int*)malloc(sizeof(int)*n);
midtree(root,arr,returnSize);
return arr;
}
注意点
1. 递归函数中对数组和元素个数的操作要注意顺序和边界。
2. 使用 malloc 分配内存后，调用者需要负责释放内存，避免内存泄漏。
四、判断一棵树是否为另一棵树的子树
思路
先判断当前两棵树是否相同（利用前面的 isSameTree 函数），如果相同则返回 true ；如果不同，则递归地在原树的左子树和右子树中继续查找是否存在与子树相同的结构。
代码实现
c
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
// 同前面判断两棵树相同的代码
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
if(root==NULL) {
return false;
}
if(isSameTree(root,subRoot)) {
return true;
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}
注意点
1. 递归调用时，要注意对空指针的处理，避免空指针异常。
2. 逻辑或 || 的使用，只要在左子树或右子树中找到匹配的子树即可。
五、补充
1. 二叉树相关题目中，递归是常用的方法，但也可以使用栈等数据结构实现非递归版本，在时间和空间复杂度上可能会有所不同。
2. 在面试中，除了写出正确的代码，还要能够清晰地阐述解题思路和时间、空间复杂度分析。
通过对这些二叉树算法题的学习和实践，我们能更好地掌握二叉树的结构和操作，为应对算法面试和实际开发中的问题打下坚实基础。