seo网站关键词优化方式,微网站建设的现状,还有哪些方法让网站更加利于seo,企业网站优化培训文章目录 根据二叉树创建字符串思路代码 二叉树的层序遍历思路代码 二叉树的最近公共祖先思路代码 二叉搜索树与双向链表思路代码 从前序与中序遍历序列构造二叉树思路代码 总结 根据二叉树创建字符串
题目#xff1a; 样例#xff1a; 可以看见#xff0c;唯一特殊的就… 文章目录 根据二叉树创建字符串思路代码 二叉树的层序遍历思路代码 二叉树的最近公共祖先思路代码 二叉搜索树与双向链表思路代码 从前序与中序遍历序列构造二叉树思路代码 总结 根据二叉树创建字符串
题目 样例 可以看见唯一特殊的就是左子树当右子树存在的时候左子树不存在的时候我们需要用()代表空但是没有左子树又没有右子树的时候我们不需要做任何处理。
思路
结合题目和样例我们可以知道特殊的是右子树存在但是左子树不存在的情况这种情况可以归类为root-left||root-right。这种情况我们就要处理左子树。首先我们应该处理一下需要返回的字符串
有左子树的情况当有左子树的时候我们直接递归左子树并将结果加上()没有左子树但是有有右子树也需要递归一次左子树因为需要加上空的()有右子树直接递归右子树最后在结果上加上()。
代码
class Solution {
public:string tree2str(TreeNode* root) {if(rootnullptr) return ;string resultto_string(root-val);if(root-left||root-right){result(tree2str(root-left));}if(root-right){result(tree2str(root-right));}return result;}
};二叉树的层序遍历
题目 样例
思路
这道题可以直接借助队列借助队列的时候我们还需要一个levelsize来记录每层的个数即可
代码
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {if(rootnullptr)return vectorvectorint();//创建队列queueTreeNode* q;q.push(root);vectorvectorint result;int levelsize1;while(!q.empty()){vectorint level;for(int i0;ilevelsize;i){auto frontq.front();q.pop();if(front-left)q.push(front-left);if(front-right)q.push(front-right);level.push_back(front-val);}result.push_back(level);levelsizeq.size();}return result;}
};二叉树的最近公共祖先
题目 样例
思路
需要找公共祖先首先我们肯定要找到这两个节点的位置然后这两个节点向上返回我们用left表示是向左子树搜索这个节点用right表示向右子树搜索这两个节点如果能找到就返回对应的节点p或者q如果没找到就返回nullptr如果left和right都不为空说明p和q分布在左子树和右子树并且root就是两个的最近的祖先如果其中一个是nullptr说明p和q分布在一边直接返回不为空的那个就是最近公共祖先。
代码
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//找对应的节点if(rootnullptr||rootp||rootq)return root;//记录左子树的结果TreeNode* leftlowestCommonAncestor(root-left,p,q);//记录右子树的结果TreeNode* rightlowestCommonAncestor(root-right,p,q);//如果左右子树都不为空则说明和q分布在左子树和右子树if(leftright)return root;//如果其中一个是空则说明p是祖先或者q是祖先return (leftnullptr)?right:left;}
};二叉搜索树与双向链表
题目 样例
思路
首先我们来看看子问题 这肯定是一个中序遍历吧因为只有中序遍历才能是顺序的这很明显接下来就是我们需要处理的中序中间的部分就是节点之间关系的转变。
从这里可以知道左指针是指向前驱的指针右指针是指向后继的指针。 这里我们分别对左子树和右子树进行中序遍历第一个遍历到4因为4是第一个所以前驱应该是nullptr因为每次我们都需要前驱所以这里我们用parent表示前驱parent就应该被初始化为nullptr当中序遍历到达4的时候4是不需要处理的因为4的左子树和右子树都是nullptr唯一需要处理的就是4的前驱应该是nullptr处理完之后我们需要返回前驱因为6需要指向前驱前驱不为空的情况下还需要将前驱的右指针指向后继4的后继是6所以我们只需要进行两个步骤第一个步骤是处理前驱前驱是已知节点指向前驱节点所以我们不用担心是否为空因为我们的前驱parent初始化是nullptr所以在parent指向后继的时候需要判断一下parent是否是空。 最后再改变前驱即可左子树的前驱就是最后一个访问的节点左中右所以上图应该是8。
代码
class Solution {
public:TreeNode* parentnullptr;void InOrder(TreeNode* root){//root是nullptr返回if(!root)return;//中序遍历InOrder(root-left);//先将root的前驱指针指向parentroot赋值给parentroot-left parent;if(parent) parent-rightroot;parent root;InOrder(root-right);}//左指针指向前面右指针指向后面TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTreenullptr)return nullptr;TreeNode* firstpRootOfTree;while(first-left) firstfirst-left;InOrder(pRootOfTree);return first;}
};从前序与中序遍历序列构造二叉树
题目 样例
思路
首先已知两个序列 前序和中序根据前序的特性我们可以知道第一个元素肯定是根节点所以这里我们可以根据前序遍历找到根节点然后在中序遍历中找到根节点的位置。 找到在中序中的位置之后我们可以通过中序的特性左边是左子树右边是右子树来对左区间和右区间递归根节点的left指向左区间根节点的right指向右区间然后循环这个过程。
代码
class Solution {
public://构建二叉树TreeNode* Build(vectorint preorder,int preL,int preR,vectorint inorder,int inL,int inR){//当左边大于右边的时候返回nullptrif(preLpreR)return nullptr;//找出根节点的值int rootvalpreorder[preL];TreeNode *rootnew TreeNode(rootval);//找到在中序遍历中的位置int indexinL;while(inorder[index]!rootval) index;//计算左子树在前序中的位置int leftSizeindex-inL;root-leftBuild(preorder,preL1,preLleftSize,inorder,inL,index-1);root-rightBuild(preorder,preLleftSize1,preR,inorder,index1,inR);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {return Build(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);}
};总结
通过多道二叉树题目的练习我们全面了解了二叉树的各种操作和特性。每道题目都涉及不同的场景和技巧如节点删除、树的遍历、以及特殊结构转换等不仅加深了对二叉树结构的理解也提升了编写递归和迭代算法的能力。这些经验为进一步深入数据结构和算法的学习打下了扎实的基础。希望这篇总结能够帮助你在二叉树题目中更得心应手为更复杂的数据结构问题做好准备。
