四川省建设厅官方网站上面查,做网站要用到什么软件,做电影网站选择什么配置的服务器,微信商城平台开发文章目录 1.二叉树的层序遍历2. 二叉树的最近公共祖先3.二叉搜索树与双向链表4.从前序与中序遍历序列构造二叉树 1.二叉树的层序遍历
二叉树的层序遍历 OJ连接 主要思路是借助一个队列#xff0c;将每一层的数据以size统计#xff0c;当size为0时说明该层数据已经输入完将每一层的数据以size统计当size为0时说明该层数据已经输入完将这一层的数据传入vector中再通过push_back 传入 vector vector int 中 class Solution {
public:string tree2str(TreeNode* root) {if(rootNULL){return ;}string s;//to_string 将任意类型转换为字符串sto_string(root-val);//只有左右子树都为空时 左子树才不加括号if(root-leftNULLroot-rightNULL){//;}else {s(;s tree2str(root-left);s);}//若右子树为空 则不加括号if(root-right!NULL){s(;s tree2str(root-right);s);}return s;}
};2. 二叉树的最近公共祖先
二叉树的最近公共祖先OJ连接 共分为三种情况
第一种情况 寻找节点7与0的公共祖先为 根节点3 节点7在根的左子树而节点0在根的右子树
若一个在根的左子树一个在根的右子树 则根就为公共祖先 第二种情况 以左子树为例 节点7与节点4属于根的左子树 节点7与节点4的最近公共祖先为 他们共同的父节点2 若两个节点都在根的左子树则递归根的左子树的节点为根判断两个节点是否为根的左右子树直到寻找到 第三种情况
节点5与节点4的最近公共祖先是节点5 节点5与节点4都属于根的左子树 若两个节点都在根的左子树则递归根的左子树的节点为根当这个根为两个节点其中一个时则这个节点就为公共祖先 由于第二种和第三种情况节点都在左子树上所以可以看作是一种情况 class Solution {
public:
bool istree(TreeNode*root,TreeNode*x)
{if(rootNULL){return false;}if(rootx){return true;}return istree(root-left,x)|| istree(root-right,x);
}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootNULL){return NULL;}//若p/q节点有一个节点为根节点则最近公共祖先为根节点if(proot||qroot){return root;}bool pleftistree(root-left,p);bool pright!pleft;bool qleftistree(root-left,q);bool qright!qleft;//两个节点分别在左右子树上if( (pleftqright)|| (prightqleft)){return root;}//两个节点都在根的左子树上则递归左子树else if(pleftqleft){return lowestCommonAncestor(root-left,p,q);}//两个节点都在根的右子树上则递归右子树else {return lowestCommonAncestor(root-right,p,q);}}
};3.二叉搜索树与双向链表
二叉搜索树与双向链表OJ连接 prev节点用于记录cur节点的上一个 当cur节点值为4时prevNULL因为4属于双向链表第一个节点值 所以没必要链接 只需更新prev的值为cur值即可 prev值不为空时将cur节点与prev节点进行连接并更新prev节点值 prev-rightcur cur-leftprev class Solution {public:void inconvert(TreeNode*cur,TreeNode*prev)//因为prev是要跟着cur进行变化的所以使用引用{if(curnullptr)return ;inconvert(cur-left,prev);//cur出现的顺序就为中序if(prev){prev-rightcur;cur-leftprev;}prevcur;inconvert(cur-right,prev);}TreeNode* Convert(TreeNode* root) {TreeNode*prevnullptr;//记录cur节点的上一个inconvert(root,prev);TreeNode*headroot;//通过遍历左子树的方式找到第一个节点while(headhead-left){headhead-left;}return head;}
}; 4.从前序与中序遍历序列构造二叉树 从前序与中序遍历序列构造二叉树OJ链接 创建root并确定值为3 在中序数组中寻找 root值为3的节点 并标记其下标为rooti 再通过递归的方式分别创建root的left与root的right 同时每次都需要prev来确定新的根 每次rooti都被赋值为inbegin是为了中序数组的新区间内寻找到根 递归结束的判断条件 若rooti与inbegin都为数组中第一个数的下标时 [inbegin, rooti-1] 即 [ 0,-1] 为不存在的区间 所以当 inbegin inright时就直接返回 class Solution {
public:
//prev为先序数组的下标
//inbeing与inend为 左右子树分割区间TreeNode*istree(vectorint preorder, vectorint inorder,int prev,int inbegin,int inend){//若rooti值与inbegin同时为第一个值//则 [inegin,rooti-1]即 [0 ,-1]会报错if(inbegininend){return nullptr;}//通过先序创建根节点TreeNode*rootnew TreeNode();root-valpreorder[prev];//在中序数组中查找root对应的值int rootiinbegin;while(rootiinend){if(preorder[prev]inorder[rooti]){break;}rooti;}prev;//由于是引用前序的根也要跟着变化//分割左右子树区间// [inbegin rooti-1] rooti [rooti1 inend]root-leftistree(preorder,inorder,prev,inbegin,rooti-1);root-rightistree(preorder,inorder,prev,rooti1,inend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i0;return istree(preorder,inorder,i,0,inorder.size()-1);}
};
