做网站时已做好了ps怎么倒入,wordpress商城模板免费下载,永久免费企业网站申请,做一个付费网站多少钱这是关于一个普通双非本科大一学生的C的学习记录贴
在此前#xff0c;我学了一点点C语言还有简单的数据结构#xff0c;如果有小伙伴想和我一起学习的#xff0c;可以私信我交流分享学习资料
那么开启正题
今天分享的是关于二叉树的题目
1.根据二叉树创建字符串
606. 根…这是关于一个普通双非本科大一学生的C的学习记录贴
在此前我学了一点点C语言还有简单的数据结构如果有小伙伴想和我一起学习的可以私信我交流分享学习资料
那么开启正题
今天分享的是关于二叉树的题目
1.根据二叉树创建字符串
606. 根据二叉树创建字符串
给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。
空节点使用一对空括号对 () 表示转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对
仔细理解题目可以发现这是一套基础的递归题要注意的是括号的省略与否左子树存在右子树不存在则可以省略左子树不存在右子树存在则不能省略
class Solution {
public:string tree2str(TreeNode* root) {string s;if(root nullptr)return s;s (to_string(root-val));if(root-left){s (;s tree2str(root-left);s );} else if(root-right){s ();}if(root-right){s (;s tree2str(root-right);s );} return s;}
};
这是ac代码
2.二叉树的层序遍历1
102. 二叉树的层序遍历
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点
二叉树的层序遍历借助queue即可但是这里需要一层一层地输出就需要做一些细微地调整具体看下面的代码
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint vv;if(root nullptr)return vv;queueTreeNode* q;q.push(root);while(!q.empty()){vectorint v;int sz q.size();for(int i 0; i sz; i){TreeNode* front q.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}vv.push_back(v);}return vv;}
};
3.二叉树的层序遍历2
107. 二叉树的层序遍历 II
给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 。 即按从叶子节点所在层到根节点所在的层逐层从左向右遍历
这题和上面很像但是是倒着遍历直接操作好像没什么头绪但是我们可以在上面题目操作完的基础上reverse以下vv即可得到结果
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint vv;if(root nullptr)return vv;queueTreeNode* q;q.push(root);while(!q.empty()){vectorint v;int sz q.size();for(int i 0; i sz; i){TreeNode* front q.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}vv.push_back(v);}reverse(vv.begin(), vv.end());return vv;}
};
这是ac代码
4.二叉树的最近公共祖先
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
很明显又是一道递归的题目要找到最近公共祖先我们从根开始判断如果有一个就是根那么直接返回根如果不是但是要判断的两个结点在树的两边子树上那么根就是最近公共祖先反之向左右子树递归解决
class Solution {
public:bool Find(TreeNode* root, TreeNode* x){ if(root nullptr)return false;if(root x)return true;return Find(root-left, x) || Find(root-right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root q || root p)return root;bool qleft, qright, pleft, pright;qleft Find(root-left, q); pleft Find(root-left, p); qright Find(root-right, q); pright Find(root-right, p);if((qleft pright) || (pleft qright))return root;if(qleft pleft)return lowestCommonAncestor(root-left, p, q);if(qright pright)return lowestCommonAncestor(root-right, q, p);return nullptr;}
};
5.二叉树与双向链表
二叉搜索树与双向链表_牛客题霸_牛客网
输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表
1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构
4.你不用输出双向链表程序会根据你的返回值自动打印输出
题目给的二叉树是搜索二叉树又叫做排序二叉树要构造一个升序的双向链表很显然要用到中序遍历而中序遍历的时候找不到他应该连的左与右所以我们借助一个子函数来完成任务
通过cur和prev与中序遍历实现双向链表的构建要注意的是prev作为“贯穿”全局的角色传参时要传引用
class Solution {
public:void _Convert(TreeNode* cur, TreeNode* prev){if(cur nullptr)return;_Convert(cur-left, prev);//处理cur-left prev;if(prev)prev-right cur;prev cur;_Convert(cur-right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev nullptr;_Convert(pRootOfTree, prev);TreeNode* head pRootOfTree;while(head head-left)head head-left;return head;}
};
这是ac代码
新手写博客有不对的位置希望大佬们能够指出也谢谢大家能看到这里让我们一起学习进步吧
