网站架构的优化,涡阳哪里有做网站的,长沙公司网站制作,ueditor 上传wordpress目录
1、根据二叉树创建字符串
2、二叉树的层序遍历
3、二叉树的最近公共祖先 4、搜索二叉树与双向链表 5、从前序与中序遍历序列构造二叉树
6、 从中序与后序遍历序列构造二叉树
7、二叉树的前序遍历#xff08;非递归实现#xff09;
8、二叉树的中序遍历#xff08…目录
1、根据二叉树创建字符串
2、二叉树的层序遍历
3、二叉树的最近公共祖先 4、搜索二叉树与双向链表 5、从前序与中序遍历序列构造二叉树
6、 从中序与后序遍历序列构造二叉树
7、二叉树的前序遍历非递归实现
8、二叉树的中序遍历非递归实现
9、二叉树的后序遍历非递归实现 1、根据二叉树创建字符串 题目要求给你二叉树的根节点 root 请你采用前序遍历的方式将二叉树转化为一个由括号和整数组成的字符串返回构造出的字符串。 例1 前序遍历完应该是1(2(3)())(5)但是2没有右孩子所以可以省略第一个括号 化简为1(2(3))(5) 例2 前序遍历完应该是1(2()(3))(5)但是2没有左孩子如果省略第一个括号会辨别不清是左孩子还是右孩子 所以依旧为1(2()(3))(5) 根据上面的样例可以明白有这样几种情况 ①左右都不为空则都不省略括号 ②左右都为空都省略括号 ③左不为空右为空可以省略右括号 ④左为空右不为空不能省略左括号 总结就是如果右不为空无论左边是否为空右边都需要加括号如果左不为空或右不为空则左边需要加括号 代码如下 class Solution {
public:string tree2str(TreeNode* root) {//若root为空则返回一个string的匿名对象if(root nullptr){return string();}//1、如果左不为空或右不为空左边需要加括号//2、如果右不为空右边需要加括号string str;//to_string将val转换为字符变量以便可以str to_string(root-val);//情况1if(root-left || root-right){str (;str tree2str(root-left);str );}//情况2if(root-right){str (;str tree2str(root-right);str );}return str;}
}; 2、二叉树的层序遍历 题目要求给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。 思路分析 我们可以创建一个队列队列中存的是二叉树的指针再给一个levelSize记录每一层的节点数在循环过程中创建一个vectorint的数组存每一层的结点val值。首先二叉树若不为空则将root存进队列中再经过判断将root的左右孩子存进队列中队列头结点pop前都将val存入v中每层结束都将v的值push_back到vv中以此类推具体代码中注释部分有 代码 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {//层序遍历一般会使用队列queueTreeNode* q;//levelSize是每一层的节点数size_t levelSize 0;//如果根节点不为空则队列中插入root节点数置为1if(root){q.push(root);levelSize 1;}//vv是需要返回的vectorvectorintvectorvectorint vv;//while循环直到队列为空while(!q.empty()){//创建vectorint v存储每一层的结点的valvectorint v;//for循环保证每次循环一层的结点for(size_t i 0;i levelSize; i){//由于每次都要删除队列的第一个值//所以front来保留一下指针以免找不到左右字树TreeNode* front q.front();q.pop();//每次删除的时候都存进vv.push_back(front-val);//如果删除结点有左右孩子都存进队列中if(front-left)q.push(front-left);if(front-right)q.push(front-right); }//每循环完一层就往vv里存一层的val值vv.push_back(v);//接着重新赋值levelSize即下一层数的节点数levelSize q.size();}return vv;}
}; 3、二叉树的最近公共祖先 题目要求给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 方法一例1 则最近公共祖先是结点2 方法一例2 则最近公共祖先是结点4 所以方法一我们可以用下面两个思路 1、如果一个是左子树中的结点一个是右子树中的结点那么它就是最近公共祖先 2、如果一个结点A是结点B的祖先那么公共祖先就是结点A 方法一的代码方法一如果遇到公共祖先在二叉树下面的部分会导致效率比较低 class Solution {
public:bool Find(TreeNode* root, TreeNode* x){//如果查找的为空返回nullptrif(root nullptr)return false;//如果找到了返回trueif(root x)return true;//如果没找到则递归进左右字树找return Find(root-left, x) || Find(root-right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root nullptr)return nullptr;//说明公共祖先是rootif((root p) || (root q))return root;//p/q在一左一右则说明当前root是公共祖先//设定4个bool类型变量与Find结合使用bool pInLeft,pInRight,qInleft,qInRight;pInLeft Find(root-left, p);pInRight !pInLeft;//在左就说明不在右所以可以用qInleft Find(root-left, q);qInRight !qInleft;//一个在左一个在右则它是公共祖先if((pInLeft qInRight) || (pInRight qInleft))return root;//若都在root左或右则递归进左或右子树中重新判断上面的条件else if(pInLeft qInleft)return lowestCommonAncestor(root-left, p, q);else if(pInRight qInRight)return lowestCommonAncestor(root-right, p, q);//此题不会进入这里因为p/q都在二叉树中elsereturn nullptr;}
}; 方法二思路相比方法一效率高点O(N) 将p和q的从根结点开始的路径放入栈中将所得两个结点的较长的路径pop到和较短路径一样长为止然后依次判断栈顶元素是否相同 思路类似链表相交 方法二例子 结点3和结点1的路径放栈里如图 结点1路径长度大pop相等后变为 接着从两个栈顶元素3和9开始判断不相同两个都pop直到遇到2返回结点2 方法二代码 class Solution {
public:bool FindPath(TreeNode* root, TreeNode* x, stackTreeNode* path){//是空返回falseif(root nullptr)return false;//不论是不是先入栈因为后面判断不是路径会poppath.push(root);//如果找到了返回trueif(root x)return true;//如果没找到进入左子树找if(FindPath(root-left,x,path))return true;//如果左子树没找到进入右子树找if(FindPath(root-right,x,path))return true;//左右字树都没找到pop掉当前栈顶元素返回falsepath.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//栈的每个元素都是TreeNode*类型stackTreeNode* pPath,qPath;//FindPath中传入的pPath和qPath都是p和q从根结点的路径FindPath(root, p, pPath);FindPath(root, q, qPath);//p/q结点的路径长度不同先变为相同路径长度while(pPath.size() ! qPath.size()){if(pPath.size() qPath.size())pPath.pop();elseqPath.pop();}//相同路径长度一层层判断顶部元素是否相同while(pPath.top() ! qPath.top()){pPath.pop();qPath.pop(); }//走到这里说明找到了相同的结点即最近祖先return pPath.top();}
}; 4、搜索二叉树与双向链表 题目要求输入一棵二叉搜索树将该二叉搜索树转换成一个排序的双向链表。如下图所示 1.要求不能创建任何新的结点只能调整树中结点指针的指向。当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode有左右指针其实可以看成一个双向链表的数据结构 思路分析 由于不能创建新的结点只能调整树中结点指针的指向所以我们就不能用先中序排好序以后再遍历的方法 那么就在中序遍历的过程中给两个指针一个prev一个curprev是指向前一个结点cur是值向当前的结点每次cur变化前都将值赋值给prev然后再将cur-left指向prev以此类推完成了left指针当前的prev就是上一个cur所以prev-right cur就是相当于上一个cur-right也指向了下一个结点从而完成了right指针 代码 class Solution {
public://中序遍历并在过程中调整结点指针的指向//cur是当前结点的指针prev是前一个结点的指针void Inorder(TreeNode* cur,TreeNode* prev){if(cur nullptr)return;//先左子树Inorder(cur-left,prev);//cur-left直接给prev因为prev是前一个结点指针cur-left prev;//若prev不为空且为TreeNode* prev是传引用即//prev-right就完成了上一个cur结点的right指针指向if(prev)prev-right cur;//在cur指向下一个之前赋值给prevprev cur;//再右子树Inorder(cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {//创建一个prev置空传入Inorder进行中序排序TreeNode* prev nullptr;Inorder(pRootOfTree, prev);//head先指定为题目所给的根结点TreeNode* head pRootOfTree;//顺着left指针找到中序遍历的第一个结点//为了防止pRootOfTree为空要先判断headwhile(head head-left)head head-left;//返回第一个结点指针return head;}
}; 5、从前序与中序遍历序列构造二叉树 题目要求给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。 思路 通过前序遍历确定根通过中序遍历确定左右字树 子树区间确认是否继续递归创建子树不存在区间则是空树 代码 class Solution {
public://创建_buildTree函数进行递归调用//prei是前序遍历结果的首元素下标inbegin、inend是中序遍历结果首尾元素的下标TreeNode* _buildTree(vectorint preorder, vectorint inorder, int prei, int inbegin, int inend){//如果在前序遍历的结果中找if(inbegin inend)return nullptr;//每次递归通过前序遍历结果创建根结点TreeNode* root new TreeNode(preorder[prei]);//while循环找到中序遍历的该结点的位置int cur inbegin;while(cur inend){if(inorder[cur] root-val)break;elsecur;}//中序遍历的结果中分成了三个部分[左子树]根[右子树]//[inbegin, cur-1] cur [cur1,inend]//所以接下来递归时传入这两个区间root-left _buildTree(preorder,inorder,prei,inbegin,cur-1);root-right _buildTree(preorder,inorder,prei,cur1,inend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {//前序遍历首元素下标为0int prei 0;//中序遍历结果首尾元素的下标为0和inorder.size()-1TreeNode* root _buildTree(preorder,inorder,prei,0,inorder.size()-1);return root;}
}; 6、 从中序与后序遍历序列构造二叉树 题目要求给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。 这个题和上面的从前序与中序遍历序列构造二叉树大体思路一样但是由于是后序确定根结点所以给定后序遍历结果的下标posi每次都会posi--并且是先递归右子树再递归左子树因为后序遍历顺序是左子树右子树根结点反过来就是根结点右子树左子树 所以代码如下 class Solution {
public:TreeNode* _buildTree(vectorint inorder, vectorint postorder,int posi,int inbegin,int inend){if(inbegin inend)return nullptr;TreeNode* root new TreeNode(postorder[posi--]);int cur inbegin;while(cur inend){if(root-val inorder[cur])break;elsecur;}//[inbegin,cur-1] cur [cur1,inend]root-right _buildTree(inorder,postorder,posi,cur1,inend);root-left _buildTree(inorder,postorder,posi,inbegin,cur-1);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int posi postorder.size()-1;return _buildTree(inorder,postorder,posi,0,inorder.size()-1);}
}; 7、二叉树的前序遍历非递归实现 题目要求给你二叉树的根节点 root 返回它节点值的 前序 遍历。 思路分析 采用非递归实现该问题能提高效率并且递归调用需要建立栈帧如果深度比较深会容易崩溃所以需要掌握非递归的方法 前序遍历中我们可以将所有结点分为左路结点以及左路结点的右子树 那么我们第一步就是将左路结点都保存下来并且存在栈中接着将存入栈的结点一个一个出栈并访问右子树然后重复上面的步骤左路结点保存入栈全部入栈后然后出栈访问该出栈结点的右子树 当左路结点从栈中出来时表示左子树以及访问过了该访问该结点和它的右子树了 就相当于转换为了子问题将所有结点分为左路结点以及左路结点的右子树接着将左路结点的右子树又分为左路结点以及左路结点的右子树以此类推从而实现非递归的方法完成前序遍历 代码如下 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* st;TreeNode* cur root;//循环条件有两个都不符合才结束循环//一是栈里空表明初始的左路结点的右子树都已访问//二是cur为空表明访问的栈中的结点的右子树为空while(cur || !st.empty()){//1、左路结点while(cur){v.push_back(cur-val);st.push(cur);cur cur-left;}//2、左树结点的右子树TreeNode* top st.top();st.pop();//将左路结点以外的数转化为上面两条的子问题//转换为子问题从而访问栈中结点的右子树cur top-right;}return v;}
}; 8、二叉树的中序遍历非递归实现 题目要求给定一个二叉树的根节点 root 返回 它的 中序 遍历 。 中序遍历和前序遍历思路大体相同但是由于中序遍历是左子树根右子树。所以中序遍历的结果需要在左路结点都入栈后再依次push_back进数组中剩下思路和前序遍历相同 代码如下 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* st;TreeNode* cur root;while(cur || !st.empty()){while(cur){st.push(cur);cur cur-left;}//左路结点都入栈后再尾插栈顶元素到数组中//依次取栈顶元素再pop转换为子问题循环TreeNode* top st.top(); st.pop();v.push_back(top-val);cur top-right;}return v;}
}; 9、二叉树的后序遍历非递归实现 题目要求给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 思路分析 后序遍历和前序/中序有一点区别因为后序是左子树右子树根我们先找到左路结点后无法确认该结点的右子树有没有访问所以就这一问题可以分类讨论 设定一个prev结点让他指向cur结点的前一个结点即每次尾插入数组时都记录当前的结点值赋值给prev这样在cur cur-right以后prev就是cur所访问的前一个结点。 将所有左路结点全部插入到栈以后分为两种情况 第一该结点的右子树为空或该结点的右子树已经访问过了第二该结点的右子树没有被访问过 第一种情况就可以访问这个栈顶结点否则先访问该结点的右子树转换为了子问题 代码 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* st;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){v.push_back(top-val);prev top;cur nullptr;st.pop();}//否则先访问栈顶结点的右子树else{cur top-right;}}return v;}
}; 相关题目列举这些
