深圳网站制作必选祥奔科技,工程承包合同协议书,wordpress用php版本,长沙网红打卡点【C二叉树】进阶OJ题 目录 【C二叉树】进阶OJ题1.二叉树的层序遍历II示例代码解题思路 2.二叉搜索树与双向链表示例代码解题思路 3.从前序与中序遍历序列构造二叉树示例代码解题思路 4.从中序与后序遍历序列构造二叉树示例代码解题思路 5.二叉树的前序遍历#xff08;非递归迭…【C二叉树】进阶OJ题 目录 【C二叉树】进阶OJ题1.二叉树的层序遍历II示例代码解题思路 2.二叉搜索树与双向链表示例代码解题思路 3.从前序与中序遍历序列构造二叉树示例代码解题思路 4.从中序与后序遍历序列构造二叉树示例代码解题思路 5.二叉树的前序遍历非递归迭代实现示例代码解题思路 6.二叉树的中序遍历非递归迭代实现示例代码解题思路 7二叉树的后序遍历非递归迭代实现示例代码解题思路 作者爱写代码的刚子 时间2023.9.6 前言本篇博客总结了一些二叉树有关的一些中等难度OJ题总结这些题的解题思路 1.二叉树的层序遍历II
题目链接
示例代码
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint vv;if(!root){return vv;}queueTreeNode* q;q.push(root);while(!q.empty()){int curlevel q.size();vv.push_back(vectorint ());while(curlevel--){TreeNode *frontq.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;}
};解题思路 选择使用队列来实现 注意这里使用变量curlevel来记录每层的元素个数并且第二个while循环中需要curlevel来计数因为题目中要求返回 vectorvector所以记录每层的元素个数是必要的。 由于题目要求返回自底向上的层序遍历所以我们还需要reverse函数将vectorvector容器进行反转。
2.二叉搜索树与双向链表
题目链接
示例代码
class Solution {
public:void test(TreeNode* cur,TreeNode* prev){if(curnullptr){return;}test(cur-left,prev);cur-leftprev;if(prev)//注意prev可能为nullptr{prev-rightcur;}prevcur;test(cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode*prevnullptr;test(pRootOfTree,prev);TreeNode* leftoverpRootOfTree;while(leftoverleftover-left){leftoverleftover-left;}return leftover;}
};
解题思路
采用中序遍历由于二叉树遍历的特殊性我们无法找到下一个遍历的对象所以我们设立新旧指针cur和prev由于根节点prev未知所以我们传入nullptr我们让cur指针先走对旧节点的指针朝向进行修改prev的left和right指针如图
本质其实就是让cur先走记录先前节点prev并修改先前节点的指针朝向。
3.从前序与中序遍历序列构造二叉树
题目链接
示例代码
class Solution {
public:TreeNode* test(vectorint preorder, vectorint inorder,int begini,int prei,int endi){if(beginiendi){return nullptr;}TreeNode* rootnew TreeNode(preorder[prei]);int rootibegini;while(rootiendi){if(preorder[prei]inorder[rooti]){break;}else{rooti;}}prei;root-lefttest(preorder, inorder,begini,prei,rooti-1);root-righttest(preorder, inorder,rooti1,prei,endi);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i0;return test(preorder,inorder,0,i,preorder.size()-1);}
};解题思路 前序遍历可以确定根节点的位置 确定了根再去中序遍历里找到对应的根 两者遍历的图示 观察图示结构我们可以将前序遍历中的数据从左到右进行遍历一次将遍历的节点作为根节点 观察图示结构我们利用前序遍历中定的根节点在中序遍历中找到对应的位置用中序遍历的结构来进行递归类似分治 递归的结束条件就是递归到子叶节点时子叶节点再进行递归递归区间有误。beginiendi
4.从中序与后序遍历序列构造二叉树
题目链接
示例代码
class Solution {
public:TreeNode*test(vectorint inorder, vectorint postorder,int begini,int prei,int endi){if(beginiendi){return nullptr;}TreeNode*rootnew TreeNode(postorder[prei]);int rootiendi;while(rootibegini){if(inorder[rooti]postorder[prei]){break;}--rooti;}--prei;root-righttest(inorder, postorder,rooti1,prei,endi);root-lefttest(inorder, postorder,begini,prei,rooti-1);//root-righttest(inorder, postorder,rooti1,prei,endi);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int ipostorder.size()-1;return test(inorder, postorder,0,i,i);}
};解题思路 思路与《从中序与后序遍历序列构造二叉树》类似先画图 我们发现与《从中序与后序遍历序列构造二叉树》这道题中的结构类似所以考虑后序遍历序列从右往左遍历依次将访问的节点作为根节点 注意后序遍历中访问完根节点后访问的是右节点所以我们应先构造右子树将《从中序与后序遍历序列构造二叉树》题中的示例代码中两个递归入口交换顺序即可
5.二叉树的前序遍历非递归迭代实现
题目链接
示例代码
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* st;TreeNode* tmproot;while(tmp||!st.empty()){while(tmp){v.push_back(tmp-val);st.push(tmp);tmptmp-left;}tmpst.top()-right;st.pop();}return v;}
};解题思路
使用vector和stack先将二叉树最左边的节点push进栈将节点储存的值push_back进vector再取出栈顶元素控制指针进入栈顶元素节点的右子树并pop该栈顶元素重复以上步骤图示
6.二叉树的中序遍历非递归迭代实现
题目链接
示例代码
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;TreeNode* curroot;while(cur||!st.empty()){while(cur){st.push(cur);curcur-left;}TreeNode* topst.top();v.push_back(top-val);curtop-right;st.pop();}return v;}
};解题思路
过程与前序遍历类似只是访问的时机不同中序遍历要在所有左子树push进栈后再进行访问并pop栈顶元素
7二叉树的后序遍历非递归迭代实现
题目链接
示例代码
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint v;TreeNode* curroot;TreeNode* prevnullptr;while(cur||!st.empty()){while(cur){st.push(cur);curcur-left;}TreeNode* topst.top();if(top-rightnullptr||top-rightprev){prevtop;v.push_back(top-val);st.pop();}else{curtop-right;}}return v;}
};解题思路
我们需要设定访问时机当右子树已经访问完了或者没有右子树时进行访问。如何判读右子树是否访问完了要引入prev指针记录上一个访问的节点判断prev是否等于当前节点top的右子树。注意这里使用的是if…else语句并不是无脑curtop-right
文章转载自： http://www.morning.zqnmp.cn.gov.cn.zqnmp.cn http://www.morning.whothehellami.com.gov.cn.whothehellami.com http://www.morning.tfkqc.cn.gov.cn.tfkqc.cn http://www.morning.xjnjb.cn.gov.cn.xjnjb.cn http://www.morning.ssjry.cn.gov.cn.ssjry.cn http://www.morning.dsprl.cn.gov.cn.dsprl.cn http://www.morning.nzcys.cn.gov.cn.nzcys.cn http://www.morning.qtwd.cn.gov.cn.qtwd.cn http://www.morning.lmmkf.cn.gov.cn.lmmkf.cn http://www.morning.qtqk.cn.gov.cn.qtqk.cn http://www.morning.pymff.cn.gov.cn.pymff.cn http://www.morning.nnhfz.cn.gov.cn.nnhfz.cn http://www.morning.snnb.cn.gov.cn.snnb.cn http://www.morning.plfy.cn.gov.cn.plfy.cn http://www.morning.qrqg.cn.gov.cn.qrqg.cn http://www.morning.gjmll.cn.gov.cn.gjmll.cn http://www.morning.wfykn.cn.gov.cn.wfykn.cn http://www.morning.lrskd.cn.gov.cn.lrskd.cn http://www.morning.hmpxn.cn.gov.cn.hmpxn.cn http://www.morning.kdpal.cn.gov.cn.kdpal.cn http://www.morning.dpwcl.cn.gov.cn.dpwcl.cn http://www.morning.nj-ruike.cn.gov.cn.nj-ruike.cn http://www.morning.qmnhw.cn.gov.cn.qmnhw.cn http://www.morning.rwlsr.cn.gov.cn.rwlsr.cn http://www.morning.znknj.cn.gov.cn.znknj.cn http://www.morning.bwznl.cn.gov.cn.bwznl.cn http://www.morning.lznqb.cn.gov.cn.lznqb.cn http://www.morning.fkyrk.cn.gov.cn.fkyrk.cn http://www.morning.jcpq.cn.gov.cn.jcpq.cn http://www.morning.fjmfq.cn.gov.cn.fjmfq.cn http://www.morning.rggky.cn.gov.cn.rggky.cn http://www.morning.bdtpd.cn.gov.cn.bdtpd.cn http://www.morning.lcwhn.cn.gov.cn.lcwhn.cn http://www.morning.rnyhx.cn.gov.cn.rnyhx.cn http://www.morning.gbkkt.cn.gov.cn.gbkkt.cn http://www.morning.pxdgy.cn.gov.cn.pxdgy.cn http://www.morning.mmynk.cn.gov.cn.mmynk.cn http://www.morning.kqzxk.cn.gov.cn.kqzxk.cn http://www.morning.rjyd.cn.gov.cn.rjyd.cn http://www.morning.pxlsh.cn.gov.cn.pxlsh.cn http://www.morning.fengnue.com.gov.cn.fengnue.com http://www.morning.prmyx.cn.gov.cn.prmyx.cn http://www.morning.jyznn.cn.gov.cn.jyznn.cn http://www.morning.trplf.cn.gov.cn.trplf.cn http://www.morning.mgzjz.cn.gov.cn.mgzjz.cn http://www.morning.hcsqznn.cn.gov.cn.hcsqznn.cn http://www.morning.mhybs.cn.gov.cn.mhybs.cn http://www.morning.qphcq.cn.gov.cn.qphcq.cn http://www.morning.jcrlx.cn.gov.cn.jcrlx.cn http://www.morning.kcrw.cn.gov.cn.kcrw.cn http://www.morning.tpxgm.cn.gov.cn.tpxgm.cn http://www.morning.jrlgz.cn.gov.cn.jrlgz.cn http://www.morning.mzcrs.cn.gov.cn.mzcrs.cn http://www.morning.yxgqr.cn.gov.cn.yxgqr.cn http://www.morning.ckhry.cn.gov.cn.ckhry.cn http://www.morning.klrpm.cn.gov.cn.klrpm.cn http://www.morning.znkls.cn.gov.cn.znkls.cn http://www.morning.htbsk.cn.gov.cn.htbsk.cn http://www.morning.pghfy.cn.gov.cn.pghfy.cn http://www.morning.dthyq.cn.gov.cn.dthyq.cn http://www.morning.nxfwf.cn.gov.cn.nxfwf.cn http://www.morning.mtsgx.cn.gov.cn.mtsgx.cn http://www.morning.ffwrq.cn.gov.cn.ffwrq.cn http://www.morning.jgcxh.cn.gov.cn.jgcxh.cn http://www.morning.jnzfs.cn.gov.cn.jnzfs.cn http://www.morning.lrnfn.cn.gov.cn.lrnfn.cn http://www.morning.xbyyd.cn.gov.cn.xbyyd.cn http://www.morning.cwgpl.cn.gov.cn.cwgpl.cn http://www.morning.fyglr.cn.gov.cn.fyglr.cn http://www.morning.ljzss.cn.gov.cn.ljzss.cn http://www.morning.nktgj.cn.gov.cn.nktgj.cn http://www.morning.zxhhy.cn.gov.cn.zxhhy.cn http://www.morning.qpsxz.cn.gov.cn.qpsxz.cn http://www.morning.wjdgx.cn.gov.cn.wjdgx.cn http://www.morning.ntlxg.cn.gov.cn.ntlxg.cn http://www.morning.symgk.cn.gov.cn.symgk.cn http://www.morning.kxbry.cn.gov.cn.kxbry.cn http://www.morning.clpdm.cn.gov.cn.clpdm.cn http://www.morning.sxmbk.cn.gov.cn.sxmbk.cn http://www.morning.ghwdm.cn.gov.cn.ghwdm.cn
