企业网站适合响应式嘛,移动互联网服务管理中心,公司网站费用,手机网站 触屏链式二叉树OJ题 一、单值二叉树#xff08;1#xff09;题目描述#xff1a;#xff08;2#xff09;思路表述#xff1a;#xff08;3#xff09;代码实现#xff1a; 二、二叉树最大深度#xff08;1#xff09;题目描述#xff1a;#xff08;2#xff09;思路… 链式二叉树OJ题 一、单值二叉树1题目描述2思路表述3代码实现 二、二叉树最大深度1题目描述2思路表述3代码实现 三、检查两颗树是否相同1题目描述2思路表述3代码实现 四、二叉树的前序遍历1题目描述2思路表述3代码实现 五、翻转二叉树1题目描述2思路表述3代码实现 六、另一颗树的子树1题目描述2思路表述3代码实现 七、二叉树的构建及遍历1题目描述2思路表述3代码实现 一、单值二叉树
1题目描述
点击链接
2思路表述
如果传回来是空节点那么就返回真。如果传过来只有一个节点那么我们也返回真首先我们应该先判断不相等的因为相等的他肯定要递归嘛最值得注意的是你得先判断这个左/右子树它存在不存在只有左/右子树存在了才能判断左/右子树中的值跟它的根节点是否相等。如果左子树不存在我们都不需要判断它如果左子树不存在我们就直接访问空了这样会报错的。如果以上的三种情况都不符合的话我们就继续递归往下走。
3代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
bool isUnivalTree(struct TreeNode* root)
{//1.如果传回来是空节点那么就返回真。if(rootNULL){return true;}//2.如果传过来只有一个节点那么我们也返回真if(root-leftNULLroot-rightNULL){return true;}//3.首先我们应该先判断不相等的因为相等的他肯定要递归嘛//最值得注意的是你得先判断这个左/右子树它存在不存在只有左/右子树存在了才能判断左/右子树中的值跟它的根节点是否相等。如果左子树不存在我们都不需要判断它如果左子树不存在我们就直接访问空了这样会报错的。if(root-leftroot-left-val!root-val){return false;}else if(root-rightroot-right-val!root-val){return false;}//4.如果以上的三种情况都不符合的话我们就继续递归往下走。return isUnivalTree(root-left)isUnivalTree(root-right);}二、二叉树最大深度
1题目描述
点击链接
2思路表述
从根开始分别遍历左子树和右子树取最大的就是整个树的最大深度
递归展开图理解
3代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/int maxDepth(struct TreeNode* root)
{if(rootNULL){return 0;}return fmax(maxDepth(root-left),maxDepth(root-right))1;
}三、检查两颗树是否相同
1题目描述
点击链接
2思路表述
1.如果两个二叉树都为空则两个二叉树相同。 2.如果两个二叉树中有且只有一个为空则两个二叉树一定不相同。
3.如果两个二叉树都不为空那么首先判断它们的根节点的值是否相同若不相同则两个二叉树一定不同若相同再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程因此可以使用深度优先搜索递归地判断两个二叉树是否相同。
3代码实现
/*** 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(pNULLqNULL){return true;}//一个为空,一个不为空if(pNULL||qNULL)//if((pNULLq!NULL)||(p!NULLqNULL)){return false;}//两个都不为空//1.先判断不相等if(p-val!q-val){return false;}//2.如果相等return isSameTree(p-left,q-left)isSameTree(p-right,q-right);}四、二叉树的前序遍历
1题目描述
点击链接 2思路表述
创建一个刚好满足所有储存树的结点的数组空间大小以前序的方式把树中的结点依次放入数组中
3代码实现
/*** 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 TreeSize(struct TreeNode* root)
{return rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;
}void Prevorder(struct TreeNode* root,int* arr,int* i)
{if(rootNULL){return;}arr[(*i)]root-val;Prevorder(root-left,arr,i);Prevorder(root-right,arr,i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{//1.创建一个刚好满足所有储存树的结点的数组空间大小int nTreeSize(root);int* arr(int*)malloc(sizeof(int)*n);int i0;//2.以前序的方式把树中的结点依次放入数组中Prevorder(root,arr,i);*returnSizen;return arr;
}五、翻转二叉树
1题目描述
点击链接
2思路表述
我们从根节点开始递归地对树进行遍历并从叶子节点先开始翻转一直遍历到树的的叶子节点如果当前遍历到的节点 root 的左右两棵子树都已经翻转那么我们只需要交换两棵子树的位置即可完成以 root 为根节点的整棵子树的翻转。
不理解的时候就画递归展开图就行
3代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*//*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*///不理解的时候就画递归展开图就行
struct TreeNode* invertTree(struct TreeNode* root)
{if(rootNULL){return NULL;}//我们从根节点开始递归地对树进行遍历并从叶子节点先开始翻转struct TreeNode* leftinvertTree(root-left);//一直遍历到树的的叶子节点struct TreeNode* rightinvertTree(root-right);root-leftright;root-rightleft;//如果当前遍历到的节点 root 的左右两棵子树都已经翻转那么我们只需要交换两棵子树的位置即可完成以 root 为根节点的整棵子树的翻转。return root;}六、另一颗树的子树
1题目描述
点击链接
2思路表述 如果root为NULL我们就返回空NULL 首先我们先判断刚开始的root和subroot的根相不相等如果相等然后再判断是否是相同的树 如果刚开始root-val!subroot-val不要着急!继续遍历root的左右子树
3代码实现
/*** 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(pNULLqNULL){return true;}//一个为空,一个不为空if(pNULL||qNULL)//if((pNULLq!NULL)||(p!NULLqNULL)){return false;}//两个都不为空//1.先判断不相等if(p-val!q-val){return false;}//2.如果相等return isSameTree(p-left,q-left)isSameTree(p-right,q-right);}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if(rootNULL){return false;}//2.首先我们先判断刚开始的root和subroot的根相不相等如果相等然后再判断是否是相同的树if(root-valsubRoot-val){if(isSameTree(root,subRoot)){return true;}//return isSameTree(root,subRoot);不能这样写因为如果这样写的话,可能root的下面可能有子树和传过来的subroot是相同的树//但是你没有判断直接return返回了这样就有所欠缺!}//3.如果刚开始root-val!subroot-val不要着急!继续遍历root的左右子树return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);}七、二叉树的构建及遍历
1题目描述
点击链接
2思路表述
读入字符串创建二叉树中序打印二叉树
3代码实现
#include stdio.h
#include stdlib.h
typedef struct TreeNode {char val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;//MakeTree函数的意义在于将数组中的数据以前序的方式创建一棵树
TreeNode* MakeTree(char* arr,int* n)
{if((arr[*n]#)||(arr[*n]\0)){return NULL;}//我要将数组中的数据放入树中的前提是我要先创造一个树。TreeNode* newtree(TreeNode*)malloc(sizeof(TreeNode));newtree-valarr[(*n)];//newtree-leftMakeTree(arr,(*n));newtree-leftMakeTree(arr,n);(*n);newtree-rightMakeTree(arr,n);return newtree;
}void InOrder(TreeNode* tree)
{if(treeNULL){return ;}InOrder(tree-left);printf(%c ,tree-val);InOrder(tree-right);
}int main() {//int n 0;//TreeSize(n);//int* arr (int*)malloc(sizeof(int) * n);//scanf(%s, arr);char arr[101];scanf(%s,arr);int n0;//创建一个n,作为一个我创建树的时候的一个标记指针如果遇到空或者结尾的时候会返回TreeNode* treeMakeTree(arr,n);InOrder(tree);return 0;
}好了今天的分享就到这里了 如果对你有帮助记得点赞关注哦 我的主页还有其他文章欢迎学习指点。关注我让我们一起学习一起成长吧
