当前位置: 首页 > news >正文

北京网站设计技术乐云seo沈阳seo技术

北京网站设计技术乐云seo,沈阳seo技术,德宏网站建设公司,phpweb手机网站模版2【C二叉树】进阶OJ题 目录 【C二叉树】进阶OJ题1.二叉树的层序遍历II示例代码解题思路 2.二叉搜索树与双向链表示例代码解题思路 3.从前序与中序遍历序列构造二叉树示例代码解题思路 4.从中序与后序遍历序列构造二叉树示例代码解题思路 5.二叉树的前序遍历(非递归迭…

【C++二叉树】进阶OJ题

目录

  • 【C++二叉树】进阶OJ题
      • 1.二叉树的层序遍历II
        • 示例代码
        • 解题思路
      • 2.二叉搜索树与双向链表
        • 示例代码
        • 解题思路
      • 3.从前序与中序遍历序列构造二叉树
        • 示例代码
        • 解题思路
      • 4.从中序与后序遍历序列构造二叉树
        • 示例代码
        • 解题思路
      • 5.二叉树的前序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路
      • 6.二叉树的中序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路
      • 7二叉树的后序遍历(非递归迭代实现)
        • 示例代码
        • 解题思路

作者:爱写代码的刚子

时间:2023.9.6

前言:本篇博客总结了一些二叉树有关的一些中等难度OJ题,总结这些题的解题思路


1.二叉树的层序遍历II

题目链接

示例代码

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;if(!root){return vv;}queue<TreeNode*> q;q.push(root);while(!q.empty()){int curlevel = q.size();vv.push_back(vector<int> ());while(curlevel--){TreeNode *front=q.front();vv.back().push_back(front->val);q.pop();if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}}reverse(vv.begin(),vv.end());return vv;}
};

解题思路

  1. 选择使用队列来实现

  2. 在这里插入图片描述

  3. 注意这里使用变量curlevel来记录每层的元素个数,并且第二个while循环中需要curlevel来计数,因为题目中要求返回 vector<vector>,所以记录每层的元素个数是必要的。

  4. 由于题目要求返回自底向上的层序遍历,所以我们还需要reverse函数将vector<vector>容器进行反转。

2.二叉搜索树与双向链表

题目链接

示例代码

class Solution {
public:void test(TreeNode* cur,TreeNode*& prev){if(cur==nullptr){return;}test(cur->left,prev);cur->left=prev;if(prev)//注意prev可能为nullptr{prev->right=cur;}prev=cur;test(cur->right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode*prev=nullptr;test(pRootOfTree,prev);TreeNode* leftover=pRootOfTree;while(leftover&&leftover->left){leftover=leftover->left;}return leftover;}
};

解题思路

  1. 采用中序遍历
  2. 由于二叉树遍历的特殊性,我们无法找到下一个遍历的对象,所以我们设立新旧指针:cur和prev,由于根节点prev未知,所以我们传入nullptr
  3. 我们让cur指针先走,对旧节点的指针朝向进行修改(prev的left和right指针)
  4. 如图:在这里插入图片描述

本质其实就是让cur先走,记录先前节点(prev),并修改先前节点的指针朝向。

3.从前序与中序遍历序列构造二叉树

题目链接

示例代码

class Solution {
public:TreeNode* test(vector<int>& preorder, vector<int>& inorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode* root=new TreeNode(preorder[prei]);int rooti=begini;while(rooti<=endi){if(preorder[prei]==inorder[rooti]){break;}else{++rooti;}}++prei;root->left=test(preorder, inorder,begini,prei,rooti-1);root->right=test(preorder, inorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return test(preorder,inorder,0,i,preorder.size()-1);}
};

解题思路

  1. 前序遍历可以确定根节点的位置

  2. 确定了根再去中序遍历里找到对应的根

  3. 两者遍历的图示:在这里插入图片描述

  4. 观察图示结构,我们可以将前序遍历中的数据从左到右进行遍历,一次将遍历的节点作为根节点

  5. 观察图示结构,我们利用前序遍历中定的根节点在中序遍历中找到对应的位置,用中序遍历的结构来进行递归(类似分治)

  6. 递归的结束条件就是递归到子叶节点时,子叶节点再进行递归,递归区间有误。(begini>endi)

4.从中序与后序遍历序列构造二叉树

题目链接

示例代码

class Solution {
public:TreeNode*test(vector<int>& inorder, vector<int>& postorder,int begini,int& prei,int endi){if(begini>endi){return nullptr;}TreeNode*root=new TreeNode(postorder[prei]);int rooti=endi;while(rooti>=begini){if(inorder[rooti]==postorder[prei]){break;}--rooti;}--prei;root->right=test(inorder, postorder,rooti+1,prei,endi);root->left=test(inorder, postorder,begini,prei,rooti-1);//root->right=test(inorder, postorder,rooti+1,prei,endi);return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i=postorder.size()-1;return test(inorder, postorder,0,i,i);}
};

解题思路

  1. 思路与《从中序与后序遍历序列构造二叉树》类似,先画图:在这里插入图片描述

  2. 我们发现与《从中序与后序遍历序列构造二叉树》这道题中的结构类似,所以考虑后序遍历序列从右往左遍历,依次将访问的节点作为根节点

  3. 注意!后序遍历中访问完根节点后访问的是右节点,所以我们应先构造右子树,将《从中序与后序遍历序列构造二叉树》题中的示例代码中两个递归入口交换顺序即可

5.二叉树的前序遍历(非递归迭代实现)

题目链接

示例代码

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> st;TreeNode* tmp=root;while(tmp||!st.empty()){while(tmp){v.push_back(tmp->val);st.push(tmp);tmp=tmp->left;}tmp=st.top()->right;st.pop();}return v;}
};

解题思路

  1. 使用vector和stack
  2. 先将二叉树最左边的节点push进栈,将节点储存的值push_back进vector
  3. 再取出栈顶元素,控制指针进入栈顶元素节点的右子树,并pop该栈顶元素,重复以上步骤
  4. 图示:在这里插入图片描述

6.二叉树的中序遍历(非递归迭代实现)

题目链接

示例代码

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}TreeNode* top=st.top();v.push_back(top->val);cur=top->right;st.pop();}return v;}
};

解题思路

过程与前序遍历类似,只是访问的时机不同,中序遍历要在所有左子树push进栈后再进行访问,并pop栈顶元素

7二叉树的后序遍历(非递归迭代实现)

题目链接

示例代码

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur=root;TreeNode* prev=nullptr;while(cur||!st.empty()){while(cur){st.push(cur);cur=cur->left;}TreeNode* top=st.top();if(top->right==nullptr||top->right==prev){prev=top;v.push_back(top->val);st.pop();}else{cur=top->right;}}return v;}
};

解题思路

  1. 我们需要设定访问时机,当右子树已经访问完了或者没有右子树时进行访问。
  2. 如何判读右子树是否访问完了:要引入prev指针记录上一个访问的节点,判断prev是否等于当前节点(top)的右子树。
  3. 注意这里使用的是if…else语句,并不是无脑cur=top->right

http://www.khdw.cn/news/54269.html

相关文章:

  • 《企业宣传片制作》百度怎么做关键词优化
  • 马鞍山集团网站设计百度百度推广
  • icp备案网站接入信息 ip地址段百度广告登录入口
  • 聊天网站站怎么做专业的网站优化公司排名
  • 公司网站企业文化怎么做友情链接代码美化
  • 网站建设职业去哪里上班大数据营销案例
  • 广东做网站公司it培训班出来工作有人要么
  • 上海建网站服务合肥网络优化公司有几家
  • 做网站的团队业绩怎么写客源引流推广
  • 人民日报网站谁做的无线网络优化工程师
  • 图片外链生成工具seo培训一对一
  • wordpress前台显示作者角色广州宣布5条优化措施
  • 宁波网站优化服务app推广平台有哪些
  • 个人主页自助建站上海关键词排名推广
  • 网站开发应用免费手机网站建站系统
  • 网站轮播图网站流量统计软件
  • 武汉做个网站多少钱朋友圈广告投放价格表
  • 单词量测试网站开发苏州seo公司
  • 用手机网站做app公司网站建设全包
  • 龙华网站(建设龙华信科)软文营销经典案例优秀软文
  • 做电影网站有什么好处小企业广告投放平台
  • 货架 网站建设 牛商网网络营销课程作业
  • wordpress博客主题自媒体淄博seo怎么选择
  • 做电梯销售从哪些网站获取信息seo关键字排名优化
  • 哪个网站做视频收益高武汉seo网络营销推广
  • 方城网站设计百度代发排名
  • 杰奇小说网站建设seo关键词排名优化评价
  • 石家庄做网站电话免费做网站怎么做网站吗
  • 枣强网址建站电话投放小网站
  • 做网站的最终目的历下区百度seo