文章目录
- 前言
- 一、力扣965. 单值二叉树
- 二、力扣100. 相同的树
- 三、力扣101. 对称二叉树
- 四、力扣144. 二叉树的前序遍历（中，后同理）
- 五、力扣572. 另一棵树的子树
- 六、牛客KY11 二叉树遍历
- 总结
前言
本文总结二叉树基础oj题型总结-C语言实现。
一、力扣965. 单值二叉树
// 第一遍自己写：（一边写，一边画图验证）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isUnivalTree(struct TreeNode* root)
{
if (NULL == root)
{
return true;// NULL为true，根据画图得
}
if ((NULL != root->left) && (root->val != root->left->val)) //如果相等就返回true，那就错了，必须所有都相等才返回true
{
return false;
}
if ((NULL != root->right) && (root->val != root->right->val))
{
return false;
}
// 每个根跟它的左右孩子都相等，返回true
return isUnivalTree(root->left) && isUnivalTree(root->right); // &&如果左为false，右不执行
}
// 方法二：遍历二叉树，用根得值和所有结点比一遍（本质和方法1相同）
二、力扣100. 相同的树
// 100. 相同的树
// 第一遍自己写：（一边写，一边画图验证）（同讲）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
// 都是空树
if (NULL == p && NULL == q)
{
return true;
}
// 如果一个为空，一个不为空，返回false
if (NULL == p || NULL == q)
{
return false;
}
// 两颗树的每个结点值都相同（或都为空）（两棵树的根和左右子树值都相同），返回true
if (p->val != q->val) // 仅仅一个结点相同不至于返回true，所以用二者不同来控制
{
return false;
}
// 说明两树的根值相同，接下来递归比较他们的左右子树
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
三、力扣101. 对称二叉树
// 101. 对称二叉树
// 第一遍自己写：（一边写，一边画图验证）（同讲）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// 创建子函数
bool _isSymmetric(struct TreeNode* left, struct TreeNode* right)
{
// 类似于判断两棵树是否相同
if (NULL == left && NULL == right)
{
return true;
}
// 一颗为空，一颗不为空
if (NULL == left || NULL == right)
{
return false;
}
// 判断每棵树的根节点，左右子树，是否对称
// 判断根节点是否对称（一个结点比较相同）（如果相同也不至于返回true），所以用二者不同来控制
if (left->val != right->val)
{
return false;
}
// 根结点对称下，对比左右子树是否对称
return _isSymmetric(left->right, right->left) && _isSymmetric(left->left, right->right);
// 可以合并为：
/*return left->val == right->val
&&_isSymmetric(left->right, right->left)
&&_isSymmetric(left->left, right->right);*/
}
bool isSymmetric(struct TreeNode* root)
{
if (NULL == root)
{
return true;
}
// 根结点不为空，判断左右子树是否对称
return _isSymmetric(root->left, root->right);
}
四、力扣144. 二叉树的前序遍历（中，后同理）
// 144. 二叉树的前序遍历（中，后同理）
// 第一遍自己写（看了指点）：（一边写，一边画图验证）（同讲）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int BTreeSize(struct TreeNode* root)
{
return NULL == root ? 0 : 1 + BTreeSize(root->left) + BTreeSize(root->right);
}
void _preorderTraversal(struct TreeNode* root, int* arr, int* pi) // 指点下才觉得子函数返回值应为空！！！！！！！！
{
if (NULL == root)
{
return; // 如果根结点为空，直接返回
}
// 前面已经判断为非空树
// 先根
arr[(*pi)++] = root->val;
// 再左子树
_preorderTraversal(root->left, arr, pi);
// 后右子树
_preorderTraversal(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
// 先要求得二叉树得结点个数，再开辟空间
int size = BTreeSize(root);
*returnSize = size;
// 空树直接返回NULL
// if(NULL == root) //其实不需要，因为后续代码包括了
// {
// return NULL;
// }
// 开辟返回数组空间
int* arr = (int*)malloc(size * sizeof(int)); // 为了避免每次都创建空间，构建子函数，指点！！！！！！！
assert(arr);
// 记录返回数组当前下标
int i = 0;
_preorderTraversal(root, arr, &i);// 传入下标地址每次递归避免了无法获取局部变量的问题
return arr;
}
五、力扣572. 另一棵树的子树
// 572. 另一棵树的子树
// 第一遍自己写：（一边写，一边画图验证）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
// 都是空树
if (NULL == p && NULL == q)
{
return true;
}
// 如果一个为空，一个不为空，返回false
if (NULL == p || NULL == q)
{
return false;
}
// 两颗树的每个结点值都相同（或都为空）（两棵树的根和左右子树值都相同），返回true
if (p->val != q->val) // 仅仅一个结点相同不至于返回true，所以用二者不同来控制
{
return false;
}
// 说明两树的根值相同，接下来递归比较他们的左右子树
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
// 如果二者均为空
if (NULL == root && NULL == subRoot)
{
return true;
}
// 如果二者其中一个为空，另一个不为空
if (NULL == root || NULL == subRoot)
{
return false;
}
// 二者均不为空
// 判断root的每一个结点是否和subRoot相同
// 所以，先判断root从根结点起和subroot是否相同，接着比较root的子结点
if (isSameTree(root, subRoot))
{
return true;
}
// 从root根结点起与subroot比较不同，则递归迭代root的左子树或者右子树是否与subroot相同
// 遍历子树的每个结点，把它当成子树的根
// 一旦找到，就返回true，如果在左子树找到则根据逻辑或的短路，右子树无须找，直接返回true
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
// 讲：
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{
if (NULL == root)
{
return false; // 其余判空情况可以交给isSametree()
}
return isSameTree(root, subRoot)
|| isSubtree(root->left, subRoot)
|| isSubtree(root->right, subRoot);
}
六、牛客KY11 二叉树遍历
// KY11 二叉树遍历
// 自己写：（有问题，没有想到用返回值链接以前的树的问题）
//#include 总结
这里对文章进行总结：
以上就是今天总结的内容，本文包括了二叉树基础oj题型总结-C语言实现，分享给大家。
真💙欢迎各位给予我更好的建议，欢迎访问！！！小编创作不易，觉得有用可以一键三连哦，感谢大家。
peace
希望大家一起坚持学习，共同进步。
梦想一旦被付诸行动，就会变得神圣。
欢迎各位大佬批评建议，分享更好的方法！！！🙊🙊🙊
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）