【初阶数据结构篇】二叉树OJ题

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++感兴趣的朋友，让我们一起进步！

1. 题目一（单值二叉树）

1.1 题目链接：

965. 单值二叉树 - 力扣（LeetCode）

1.2 题目描述

补充：

 根节点与左右孩子的数值进行比较，如果相等依次递归左右子树，如果为空，或者两者对应的值相等，则返回true。若不相等则直接返回false。

1.3 示例代码：

class Solution {
public:bool isUnivalTree(TreeNode* root) {if(root==NULL){return true;}if(root->left&&root->left->val!=root->val){return false;}if(root->right&&root->right->val!=root->val){return false;}if(isUnivalTree(root->left)&&isUnivalTree(root->right))return true;else{return false;}}
};

2. 题目2（相同的树）

2.1 题目链接：

100. 相同的树 - 力扣（LeetCode）

2.2 题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

补充：

题目解析：

将两个数的根节点的值依次比较，依次递归两根节点的左子树，若根节点为空，直接返回true，或两根节点对应的值相等也返回true，对应的值不相等或一个根节点为空而另一个不为空直接返回false。 

2.3 示例代码：

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(p==NULL&&q==NULL){return true;}if(p==NULL||q==NULL){return false;}if(p->val!=q->val){return false;}if(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right))return true;else{return false;}}
};

3. 题目3（对称二叉树）

3.1 题目链接：

100. 相同的树 - 力扣（LeetCode）

3.2 题目描述

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

 

可以将该二叉树看成两个独立的二叉树，分别将“两个二叉树”的根节点传入，判断该是否为相同的二叉树。

3.3 示例代码：
 

bool isSameTree(TreeNode* p, TreeNode* q) {if(p==NULL&&q==NULL){return true;}if(p==NULL||q==NULL){return false;}if(p->val!=q->val){return false;}if(isSameTree(p->left,q->right)&&isSameTree(p->right,q->left))return true;else{return false;}
}class Solution {
public:bool isSymmetric(TreeNode* root) {return isSameTree(root->left,root->right);}
};

4. 题目4（另一棵树的子树）

4.1 题目链接：

572. 另一棵树的子树 - 力扣（LeetCode）

4.2 题目描述：

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

依次递归每个节点，将每个节点与SunRoot判断是否相等即可。

4.3 示例代码：

bool isSameTree(TreeNode* p, TreeNode* q) {if(p==NULL&&q==NULL){return true;}if(p==NULL||q==NULL){return false;}if(p->val!=q->val){return false;}if(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right))return true;else{return false;}
}class Solution {
public:bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(root==NULL){return false;}if(isSameTree(root,subRoot)){return true;}return( isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot));}
};

5. 题目5（二叉树前序遍历）

5.1 题目链接：

144. 二叉树的前序遍历 - 力扣（LeetCode）

5.2 题目描述

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

 

给二叉树中节点总数开空间，根据根左右原则依次递归将数据尾插入数组中，直接返回这个数组即可。

5.3 示例代码：

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

 

相信通过这篇文章你对二叉数OJ题的有了进一步的了解。如果此篇文章对你学习数据结构（二叉树）有帮助，期待你的三连，你的支持就是我创作的动力！！！

下一篇文章再会！！！