网站换ip注意,帮人做网站要怎么赚钱,网络营销主要学些什么,沈阳工务轨道建设网站首先我们先回忆我们过去学的二叉树和最近学的二叉搜索树,来完成下面的题目:
606. 根据二叉树创建字符串
这道题属于与基础题,首先我们观察输入输出样例可以得到如果root-left为空,root-right不为空时,我们的空格仍然需要保留,如果当前节点有两个孩子#xff0c;那我…首先我们先回忆我们过去学的二叉树和最近学的二叉搜索树,来完成下面的题目:
606. 根据二叉树创建字符串
这道题属于与基础题,首先我们观察输入输出样例可以得到如果root-left为空,root-right不为空时,我们的空格仍然需要保留,如果当前节点有两个孩子那我们在递归时需要在两个孩子的结果外都加上一层括号如果当前节点没有孩子那我们不需要在节点后面加上任何括号如果当前节点只有左孩子那我们在递归时只需要在左孩子的结果外加上一层括号而不需要给右孩子加上任何括号
代码示例:
class Solution {
public:string tree2str(TreeNode* root) {string str;if(rootnullptr){return str;}strto_string(root-val);if(root-left||root-right){ str(;strtree2str(root-left);str);}if(root-right){str(;strtree2str(root-right);str);}return str;}
}; 102. 二叉树的层序遍历 我们可以通过队列来解决 核心思想:我们在层序遍历过程中增加一-个levelSize,记录每层的数据个数树不为空的情况下,第1层levelSize1,循环控制第1层出完了第2层就都进队列了队列中size就是第2层的数据个数。以此内推,假设levelSize为第n层的数据个数因为层序遍历思想为当前层结点出队列带入下一层结点(也就是子结点),循环控制第n层数据出完了那么第n1结点都进队列了队列size,就是下一层的levelSize。 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint vv;queueTreeNode* q;int levelsize0;if(root){q.push(root);levelsize1;}while(levelsize){vectorint v;while(levelsize--){TreeNode*frontq.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}levelsizeq.size();vv.push_back(v);}return vv;}
};
107. 二叉树的层序遍历 II 上题我们搞完了,这题我们其实有个很简单的办法,我们把上题的代码赋值过来直接逆置即可
代码示例:
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {vectorvectorint vv;queueTreeNode* q;int levelsize0;if(root){q.push(root);levelsize1;}while(levelsize){vectorint v;while(levelsize--){TreeNode*frontq.front();q.pop();v.push_back(front-val);if(front-left)q.push(front-left);if(front-right)q.push(front-right);}vv.push_back(v);levelsizeq.size();}reverse(vv.begin(),vv.end());return vv;}
}; 236. 二叉树的最近公共祖先 本题思路有二,我们一个一个来讲
方法一递归 首先我们对于题意进行分析,我们可以知道公共祖先分为以下几种情况: 1.p或q在root节点处,此时最近的公共祖先就是root 2.p和q分别分布在root的左右子树,此时公共祖先就是root 3.p和q分布在root的同一子树,此时我们可以把该子节点看作root,继续判断。 代码实现
class Solution {
public:bool Intree(TreeNode* t,TreeNode* x){if(!t){return false;}return xt||Intree(t-left,x)||Intree(t-right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootp||rootq){return root;}bool pinleftIntree(root-left,p);bool pinright!pinleft;bool qinleftIntree(root-left,q);bool qinright!qinleft;if((pinleftqinright)||(pinrightqinleft)){return root;}else if(pinleftqinleft){return lowestCommonAncestor(root-left,p,q);}else{return lowestCommonAncestor(root-right,p,q);}}
};
下面我们来讲讲第二种方法
思路2:如果能求出两个结点到根的路径那么就可以转换为链表相交问题。如: 6到根3的路径为6-5-3, 4到根3的路径为4-2-5-3,那么看做两个链表找交点交点5就是最近公共祖先。 代码示例:
class Solution {
public:bool GetPath(TreeNode* root,TreeNode* x,stackTreeNode* path){if(rootnullptr)return false;path.push(root);if(rootx)return true;if(GetPath(root-left,x,path))return true;if(GetPath(root-right,x,path))return true;path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* ppath,qpath;GetPath(root,p,ppath);GetPath(root,q,qpath);//确定长度while(ppath.size()!qpath.size()){//长的先if(ppath.size()qpath.size()){ppath.pop();}else{qpath.pop();}}//找交点while(ppath.top()!qpath.top()){ppath.pop();qpath.pop();}//输出交点return ppath.top();}
}; JZ36 二叉搜索树与双向链表 这题在我们学完二叉搜索树之后大家应该觉得不难吧,核心思想:中序遍历
代码示例:
#include cstddef
class Solution {
public:TreeNode* headnullptr;TreeNode* curnullptr;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTreenullptr)return nullptr;Convert(pRootOfTree-left);if(curnullptr){headpRootOfTree;curpRootOfTree;}else {cur-rightpRootOfTree;pRootOfTree-leftcur;curpRootOfTree;}Convert(pRootOfTree-right);return head;}
};
105. 从前序与中序遍历序列构造二叉树 本题咋一看很简单,仔细一看好像有点难,但是一看提示,瞬间就来了思路,其实很简单是不是.
我的思路:根据前序确定根然后再中序中确定根所处的位置分割两个区间然后递归即可。递归截止的条件为当左右不构成区间。
代码示例:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* build(vectorint preorder, vectorint inorder, int prei, int inbegin, int inend) {if(inbegininend)return nullptr;//前序确定根TreeNode* rootnew TreeNode(preorder[prei]);//中序分割左右子树int rootiinbegin;while(rootiinend){if(preorder[prei] inorder[rooti])break;elserooti;}prei;root-leftbuild(preorder,inorder,prei,inbegin,rooti-1);root-rightbuild(preorder,inorder,prei,rooti1,inend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i0;return build(preorder,inorder,i,0,inorder.size()-1);}
};
106. 从中序与后序遍历序列构造二叉树 这题是上一题的兄弟题,我们直接上代码了,不懂的再想想,画画递归展开图
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* build(vectorint inorder, vectorint postorder,int posti,int inbegin,int inend){if(inbegininend)return nullptr;TreeNode* newnodenew TreeNode(postorder[posti]);int inposinbegin;while(inposinend){if(postorder[posti]inorder[inpos]){break;}inpos;}posti--;newnode-right build(inorder,postorder,posti,inpos1,inend);newnode-left build(inorder,postorder,posti,inbegin,inpos-1);return newnode;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int ipostorder.size()-1;return build(inorder,postorder,i,0,inorder.size()-1);}
};
