刷题|＜数据结构＞来，一起刷题吧——二叉树（单值二叉树、相同的树、对称二叉树、另一棵树的子树、前序遍历） c语言|数据结构|后端|数据结构

文章图片

文章目录

1. 单值二叉树
- 链接
- 思路
- 参考代码
2. 相同的树
- 链接
- 思路
- 参考代码
3. 对称二叉树
- 链接
- 思路
- 参考代码
4. 另一棵树的子树
- 链接
- 思路
- 参考代码
5. 二叉树的前序遍历
- 链接
- 思路
- 参考代码

目前在不断更新<数据结构>的知识总结，已经更新完了，未来我会系统地更新等内容。

上一篇相关博客：＜数据结构＞链式二叉树的基本操作
本文是在上一篇相关博客的基础上进阶的刷题训练，如果不熟悉分治的思想，建议先看那篇
1. 单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：

文章图片
输入：[1,1,1,1,1,null,1]
输出：true

示例 2：

文章图片
输入：[2,2,2,5,2]
输出：false

提示：
给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99] 。

链接力扣965. 单值二叉树
思路

有两种思路:
1??遍历一遍，所有的值都跟根的值相同就为真，否则为假
2??所有的子树和根的值都相同返回真，否则为假

参考代码运用方法二的思路

bool isUnivalTree(struct TreeNode* root){ if(root == NULL) return true; if(root->left && root->val != root->left->val) return false; if(root->right && root->val != root->right->val) return false; return isUnivalTree(root->left) && isUnivalTree(root->right); }

2. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

文章图片
输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

文章图片
输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

文章图片
输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

链接力扣100. 相同的树
思路

相同则继续运行，一旦不同就返回false。
1??都为空，返回true
2??只有一个为空（结构不同），返回false
3??都不为空，数值不同，返回false。数值相同，继续执行
再递归判断左子树，右子树是否都相同

参考代码

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); }

3. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

文章图片
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

文章图片
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？

链接力扣101. 对称二叉树
思路

把根节点去掉，拆成两个小二叉树
就变得跟上一题很像，但要注意是对称相同

参考代码

bool _isSymmetric(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 _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left); }bool isSymmetric(struct TreeNode* root){ //防止根为空 if(root == NULL) return true; return _isSymmetric(root->left, root->right); }

4. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

文章图片
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

文章图片
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

链接力扣572. 另一棵树的子树
思路

这跟第二题又是个姐妹题，就把二叉树遍历一下，判断不同的根节点下有没有相同的树。
嘻嘻，直接把之前写的函数搞过来用。

参考代码

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); }bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ if(root == NULL) return false; return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right,subRoot); //遍历这棵树 }

5. 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

文章图片
输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：

文章图片
输入：root = [1,2]
输出：[1,2]

示例 5：

文章图片
输入：root = [1,null,2]
输出：[1,2]

提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？

链接力扣144. 二叉树的前序遍历
思路

前序遍历的思路上个文章讲到过
这题要注意一些之前没遇到的问题：
数组要malloc出来用，malloc的空间大小要自己算出来，防止不够用
并且把空间大小赋值给*returnSize
前序遍历时数组的下标要传指针，防止递归调用时下标被覆盖
举个：

刷题|＜数据结构＞来，一起刷题吧——二叉树（单值二叉树、相同的树、对称二叉树、另一棵树的子树、前序遍历）

文章图片

参考代码

int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->right)+TreeSize(root->left)+1; }void _preorder(struct TreeNode* root, int* a, int* pi) { if(root == NULL) return; a[(*pi)++] = root->val; _preorder(root->left, a, pi); _preorder(root->right, a, pi); }int* preorderTraversal(struct TreeNode* root, int* returnSize){ int size = TreeSize(root); int* a = malloc(sizeof(int)*size); *returnSize = size; int i = 0; _preorder(root, a, &i); return a; }