【数据结构初阶第十七节】二叉树算法题_二叉树 竞赛 选择题

Hi！

必须有为成功付出代价的决心，然后想办法付出这个代价。云边有个稻草人-CSDN博客 

目录

一、单值二叉树

二、相同的树

三、对称二叉树

四、另一棵树的子树

五、二叉树遍历

（1）前序遍历

（2）中序遍历

（3）后序遍历

六、二叉树的构建及遍历

七、二叉树选择题

Relaxing Time——

             —————————————— 《 像极了 》 ——————————————

正文开始——接受挑战！

一、单值二叉树

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

【图解】 

【思路】

就是从根节点开始不断遍历，先遍历左子树，遍历到一个节点的时候判断该节点的左节点是否和该结点的值相等，再判断该节点的右节点是否和该结点相等，就这样不断地递归，return，注意，我们使用递归一定要注意递归结束的条件，本题递归结束的条件是root == NULL时结束。下面是代码+注释，照着代码把递归过程顺一遍，用箭头来代表函数栈帧的创建与销毁就没那么抽象了。把上节学的递归搞熟悉之后理解本题的递归就不是大问题。下一题—— 

【代码】 

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */typedef struct TreeNode TreeNode;bool isUnivalTree(struct TreeNode* root) { //递归结束的条件（找递归结束的条件还是很重要的） if(root == NULL) { return true;//直接return，root == NULL不影响结果，直接返回 } //先判断root的左节点是否和根节点值相同，这里是不相同直接return false（注意这里的用法） if(root->left && root->left->val != root->val) { return false; } //再判断右节点是否和根节点相同，和上面同样的道理 if(root->right && root->right->val != root->val) { return false; } //紧接着递归,判断root->left和root->right，也就是root的左右子树 return isUnivalTree(root->left) && isUnivalTree(root->right); }

二、相同的树

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

【图解】 

【代码】

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */typedef struct TreeNode TreeNode; bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //当两个节点都为NULL时,相等 if(p == NULL && q == NULL) { return true; } //当两个节点其一为NULL，不相等 if(p == NULL || q == NULL) { return false; } //两个节点都不为NULL，这时判断不相等才能说明问题 if(p->val != q->val) { return false;//这是根节点不相同时 } //注意这里是&&，必须左右节点都相等返回True时才可以判断相等 return isSameTree(p->left,q->left) && isSameTree(p->right,q->right); }

三、对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

本题会借助上题的思路，看看自己能不能做出来

【图解】

【代码】 

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //当两个节点都为NULL时,相等 if(p == NULL && q == NULL) { return true; } //当两个节点其一为NULL，不相等 if(p == NULL || q == NULL) { return false; } //两个节点都不为NULL，这时判断不相等才能说明问题 if(p->val != q->val) { return false;//这是根节点不相同时 } //这里判断节点是否相同，注意传参的内容 return isSameTree(p->left,q->right) && isSameTree(p->right,q->left); }bool isSymmetric(struct TreeNode* root) { //调用上面的判断树是否相等的函数，注意这里传的形参,返回判断树是否相同的结果true/false return isSameTree(root->left,root->right);}

四、另一棵树的子树

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

【图解】

【代码】 

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //当两个节点都为NULL时,相等 if(p == NULL && q == NULL) { return true; } //当两个节点其一为NULL，不相等 if(p == NULL || q == NULL) { return false; } //两个节点都不为NULL，这时判断不相等才能说明问题 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; } //从根节点判断树是否相等 if(isSameTree(root,subRoot)) { return true; } //再去递归root树的左子树，判断与subRoot是否相等 return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);}

五、二叉树遍历

（1）前序遍历

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

【图解】

【代码】 

/** * 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(). */typedef struct TreeNode TreeNode;int TreeSize(TreeNode* root){ //总的节点个数 = 根节点1 + 左子树结点个数 + 右子树结点个数 if(root == NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right);}void _preorderTraversal(TreeNode* root,int* arr,int* pi){ //前序遍历 根 左 右 if(root == NULL) { return; } arr[(*pi)++] = root->val; _preorderTraversal(root->left,arr,pi); _preorderTraversal(root->right,arr,pi);}int* preorderTraversal(struct TreeNode* root, int* returnSize) { //我们要将树遍历的结果放到数组里面，所以我们要动态创建一个数组 //1.获取树的结点的个数，为动态开辟数组内存空间做准备 *returnSize = TreeSize(root); //2.动态开辟一块空间 int* returnArr = (int*)malloc(sizeof(int)*(*returnSize)); //3.前序遍历树并存入到数组里面 int i = 0; _preorderTraversal(root,returnArr,&i); return returnArr;}

（2）中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

中序遍历和前序遍历对于这道题来说其实都是一样的，只是其中遍历的方式不一样，整体思路是一样的，后序遍历亦是如此，前面的前、中、后序遍历学得OK的话实现这两道就没有任何问题。

【代码】

/** * 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(). */typedef struct TreeNode TreeNode;int TreeSize(TreeNode* root){ //总的节点个数 = 根节点1 + 左子树结点个数 + 右子树结点个数 if(root == NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right);}void _inorderTraversal(TreeNode* root,int* arr,int* pi){ //中序遍历 左 根 右 if(root == NULL) { return; } _inorderTraversal(root->left,arr,pi); arr[(*pi)++] = root->val; _inorderTraversal(root->right,arr,pi);}int* inorderTraversal(struct TreeNode* root, int* returnSize) { //我们要将树遍历的结果放到数组里面，所以我们要动态创建一个数组 //1.获取树的结点的个数，为动态开辟数组内存空间做准备 *returnSize = TreeSize(root); //2.动态开辟一块空间 int* returnArr = (int*)malloc(sizeof(int)*(*returnSize)); //3.前序遍历树并存入到数组里面 int i = 0; _inorderTraversal(root,returnArr,&i); return returnArr;}

（3）后序遍历

145. 二叉树的后序遍历 - 力扣（LeetCode）

【代码】

/** * 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(). */typedef struct TreeNode TreeNode;int TreeSize(TreeNode* root){ //总的节点个数 = 根节点1 + 左子树结点个数 + 右子树结点个数 if(root == NULL) { return 0; } return 1 + TreeSize(root->left) + TreeSize(root->right);}void _postorderTraversal(TreeNode* root,int* arr,int* pi){ //中序遍历 左 根 右 if(root == NULL) { return; } _postorderTraversal(root->left,arr,pi); _postorderTraversal(root->right,arr,pi); arr[(*pi)++] = root->val;}int* postorderTraversal(struct TreeNode* root, int* returnSize) { //我们要将树遍历的结果放到数组里面，所以我们要动态创建一个数组 //1.获取树的结点的个数，为动态开辟数组内存空间做准备 *returnSize = TreeSize(root); //2.动态开辟一块空间 int* returnArr = (int*)malloc(sizeof(int)*(*returnSize)); //3.前序遍历树并存入到数组里面 int i = 0; _postorderTraversal(root,returnArr,&i); return returnArr;}

六、二叉树的构建及遍历

二叉树遍历_牛客题霸_牛客网

其实这道题整体不是很难，代码里面用到的申请结点，中序遍历啥的我们前面都写过，就是思路的第二点难些需要我们自己写一个二叉树递归的创建。

这是牛客网上的题，所有的都要自己实现，头文件也要自己写。

【代码】

#include #includetypedef struct BinaryTreeNode{ char data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;}BTNode;BTNode* buyNode(char x){ BTNode* newnode = (BTNode*)malloc(sizeof(BTNode)); newnode->data = x; newnode->left = newnode->right = NULL; return newnode;}BTNode* createTree(char* arr,int* pi){ //递归结束的条件 if(arr[(*pi)] == \'#\') { (*pi)++; return NULL; } BTNode* root = buyNode(arr[(*pi)++]); root->left = createTree(arr,pi); root->right = createTree(arr,pi); return root;}//中序遍历void InOrder(BTNode* root){ if(root == NULL) { return; } InOrder(root->left); printf(\"%c \",root->data); InOrder(root->right);}int main() { //1.读取用户的输入并存入到数组里面 char arr[100]; scanf(\"%s\",arr); //2.根据前序遍历字符串创建二叉树 int i = 0; BTNode* root = createTree(arr,&i); //3.中序遍历二叉树 InOrder(root); return 0; }

好了，到这里OJ题就告一段落了，下面开展选择题——

七、二叉树选择题

我们要先学习二叉树的一个性质

（1）对任何⼀棵⼆叉树, 如果度为 0 其叶结点个数为 n 0 , 度为 2 的分⽀结点个数为 n 2 ,则有 n 0 = n 2 + 1

学完这个性质我们来练练选择题，我们先独立做一下，题目后面有答案+解析

 【解析】

链式二叉树遍历选择题

【解析】 

本篇关于链式二叉树的习题就结束了，课下要多思考多自己实现代码多实践！

别害怕，即使很难也要前进，只不过是速度慢一点，也总比原地踏步的好，你觉得难，别人自然也不会觉得简单，别人都能学，我们为什么要退缩呢？前面一节我学习二叉链里面的递归一开始也觉得挺难的，但是我们可以尝试把它当做一块硬骨头，虽然难，但是我们一点一点的啃，一点一点的攻破，多整体思考几次也就觉得没那么难了，甚至自己都会写了。既然选择了这条路我就要坚定地走下去！

依旧是认真地完成了本节课的博客，下节课学习排序。。。

完——

Relaxing Time——

跟你分享一首歌吧

             —————————————— 《 像极了 》 ——————————————

像极了_永彬Ryan.B_高音质在线试听_像极了歌词|歌曲下载_酷狗音乐

至此结束——

我是云边有个稻草人

期待与你的下一次相遇。。。拜~~~