做教育网站,wordpress怎么换空间,企业管理培训课程价格,医院网站开发多少钱励志冰檗#xff1a;形容在清苦的生活环境中激励自己的意志。#x1f493;#x1f493;#x1f493; 目录 说在前面
题目一#xff1a;单值二叉树
题目二#xff1a;相同的树
题目三#xff1a;对称二叉树
题目四#xff1a;二叉树的前序遍历
题目五#xff1a;另… 励志冰檗形容在清苦的生活环境中激励自己的意志。 目录 说在前面
题目一单值二叉树
题目二相同的树
题目三对称二叉树
题目四二叉树的前序遍历
题目五另一棵树的子树
题目六二叉树的构建及遍历
SUMUP结尾 说在前面 dear朋友们大家好我们又见面了又到了我们数据结构的刷题时间了。我们上次刚学完了二叉树的知识现在就让我们来练练手~ 友友们点击这里进入力扣leetcode学习 以下是leetcode题库界面 点击这里进入牛客网NowCoder刷题学习 以下是NowCoder题库界面 题目一单值二叉树
题目链接965. 单值二叉树 - 力扣LeetCode
题目描述 题目分析
思路对于二叉树的OJ练习我们一定要多利用递归的思想即将大问题拆成子问题。首先我们考虑如果树为空显然也是单值二叉树返回true如果节点中的值与它左右子树根节点的值不同那肯定返回false如果和它左右子树根节点的值都相同就递归到左右子树按照同样的逻辑即可。
代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root) {if(root NULL)return true;if(root-left root-val ! root-left-val || root-right root-val ! root-right-val)return false;return isUnivalTree(root-left) isUnivalTree(root-right);
}
题目二相同的树
题目链接100. 相同的树 - 力扣LeetCode
题目描述 题目分析
思路首先我们需要判断这两棵树是否为空如果都为空那么也是相同的树如果其中有一个为空另一个不为空那就不是相同的树如果第一棵树和第二棵树的值不相等那肯定不是相同的树如果它们的值相等就需要递归到左右子树如果左右子树都满足自然最终会回到第一种情况再将true回归。 代码如下
/*** 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(!p !q)return true;if(!p || !q)return false;return p-val ! q-val ? false : isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}
题目三对称二叉树
题目链接101. 对称二叉树 - 力扣LeetCode
题目描述 题目分析
思路这道题的思路和题目二有些许类似题目二是判断两棵树的左右子树是否相同而这道题是判断你的左子树和我的右子树是否相同即可也就是我们把二叉树分为root-left和root-right利用和题目二相同的逻辑就可以了。
代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) {if(!p !q)return true;if(!p || !q)return false;return p-val ! q-val ? false : _isSymmetric(p-left, q-right) _isSymmetric(p-right, q-left);
}bool isSymmetric(struct TreeNode* root) {return _isSymmetric(root-left, root-right);
}
题目四二叉树的前序遍历
题目链接144. 二叉树的前序遍历 - 力扣LeetCode
题目描述 题目分析
思路我们再上一章二叉树的部分学习过二叉树的前序遍历但我们之前的前序遍历在遍历过程中的操作是打印节点的值我们现在的操作是把它存在一个数组arr中。那数组的大小*returnSize是多少呢显然就是树的节点所以我们也需要TreeSize函数来计算树的节点。
代码如下
/*** 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)
{if(root NULL)return 0;return TreeSize(root-left) TreeSize(root-right) 1;
}//前序遍历
void PrevOrder(TreeNode* root, int* arr, int* pi)
{if(root NULL)return;arr[(*pi)] root-val;PrevOrder(root-left, arr, pi);PrevOrder(root-right, arr, pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize TreeSize(root);int* arr (int*)malloc((*returnSize) * sizeof(int));int i 0;PrevOrder(root, arr, i);return arr;
}
注意i作为数组arr的下标会随着递归的深度而进行改变所以需要传址调用。
题目五另一棵树的子树
题目链接572. 另一棵树的子树 - 力扣LeetCode
题目描述 题目分析
思路这道题我们首先判断root本身是否为空如果本身为空显然subRoot不可能是root的子树。如果root不为空我们判断root和subRoot是否是相同的树相同的树也算true如果是就返回true如果不是就递归到它的左右子树即可。所以我们还需要用到题目二中的相关代码。
代码如下
/*** 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(!p !q) return true;if(!p || !q) return false;return p-val ! q-val ? false : 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) ? true :isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);
}
题目六二叉树的构建及遍历
题目链接二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
题目描述
题目分析
思路这道题依旧用到了我们上一章中前序和中序遍历的思想首先构建二叉树我们需要将前序遍历存放在数组arr中用i作为下标。和题目五类似i也需要传地址调用。
代码如下
#include stdio.h
#include stdlib.h#define MAXSIZE 100typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//二叉树的构建
BTNode* CreateTree(char* arr, int* pi)
{BTNode* root (BTNode*)malloc(sizeof(BTNode));if(arr[*pi] #){(*pi);return NULL;}root-data 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()
{char arr[MAXSIZE];scanf(%s,arr);int i 0;BTNode* root CreateTree(arr, i);InOrder(root);return 0;
} SUMUP结尾 数据结构就像数学题需要刷题才能对它有感觉。之后还会更新数据结构相关的练习题、面试题希望大家一起学习共同进步~ 如果大家觉得有帮助麻烦大家点点赞如果有错误的地方也欢迎大家指出~
