团购网站 模板,建立团购网站,网页设计作业html博物馆免费,html做网站怎么链接音乐文章目录 二叉树创建字符串二叉树分层遍历#xff08;从前开始#xff09;二叉树分层遍历#xff08;从后开始#xff09;二叉树的最近公共祖先二叉搜索树与双向链表从前序与中序遍历序列构造二叉树从中序与后序遍历序列构造二叉树二叉树的前序遍历#xff08;非递归… 文章目录 二叉树创建字符串二叉树分层遍历从前开始二叉树分层遍历从后开始二叉树的最近公共祖先二叉搜索树与双向链表从前序与中序遍历序列构造二叉树从中序与后序遍历序列构造二叉树二叉树的前序遍历非递归二叉树的中序遍历非递归二叉树的后续遍历 二叉树创建字符串 思路 该题需要注意的细节就是当节点的左子树为空而右子树却不为空的情况就需要特殊处理也是需要加上()而节点的左子树不为空右子树为空就是不需要加上()。if(root-left||root-right)该语句就是实现左子树的字符和()之后再去处理右子树。 //C
class Solution {
public:string tree2str(TreeNode* root) {if(rootnullptr){return ;}string strto_string(root-val);if(root-left||root-right){str(;strtree2str(root-left);str);}if(root-right){str(;strtree2str(root-right);str);}return str;}
};二叉树分层遍历从前开始 **思路**创建一个队列将遍历的数据存入到里面在创建一个计数器用来记录每层的数据个数。 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* q;vectorvectorint vv; int levelsize0;if(root){q.push(root);levelsize1;}while(!q.empty()){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();}return vv;}
};二叉树分层遍历从后开始 **思路**其实他就和上一个题的思路是一样的只需要加个翻转就可以了。 class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode* q;vectorvectorint vv; int levelsize0;if(root){q.push(root);levelsize1;}while(!q.empty()){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;}
};二叉树的最近公共祖先 思路 1、使用三叉链有父节点转换为链表相交问题其中长的一条先走gap。 2、就是进行判断确定一个数在自己的左边另一个在自己的右边。不在用一边就说明现在的节点就是最近的公共祖先在同一边就需要继续向下找。 class Solution {
public:bool Isintree(TreeNode* root,TreeNode* in){if(rootnullptr){return false;}if(rootin){return true;}else{return Isintree(root-left,in) || Isintree(root-right,in);}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootnullptr){return nullptr;}if(proot || qroot){return root;}bool pinleftIsintree(root-left,p);bool pinright!pinleft;bool qinleftIsintree(root-left,q);bool qinright!qinleft;if((pinleft qinright) || (pinright qinleft)){return root;}else if(pinleftqinleft){return lowestCommonAncestor(root-left,p,q);}else{return lowestCommonAncestor(root-right,p,q);}}
};注意 上面的写法是属于性能较低的他所用的时间是较长的。时间复杂度是O(N^2)。在他最坏的情况下会出现歪脖子树。也就是确定一次两个数在哪边递归一边查找歪脖子树共要向下递归N次。 思路 下面的思路就是找到两条路径用找链表的公共节点的方法来找最近公共节点。需要注意的就是在放入栈之后要进行判断下面没有就要进行出栈。 class Solution {
public:bool Getpath(TreeNode* root, TreeNode* g,stackTreeNode* path){if(rootnullptr){return false;}path.push(root);//只要不是空就放进来if(rootg){return true;}if(Getpath(root-left,g,path)){return true;}if(Getpath(root-right,g,path)){return true;}path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode* qpath,ppath;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();}
};二叉搜索树与双向链表 思路 该题目要求了空间复杂度要是不要求的话直接就中序遍历就好了。将节点prev指向空cur为4的指针这里要注意成员函数prev的引用是必须要带上的不带会影响整个结构的。将cur以递归的路径进行prev跟上cur之前的节点。通过cur-leftprevprev-rightcur。 class Solution {
public:void InorderConvert(TreeNode* cur,TreeNode* prev){if(curnullptr){return;}InorderConvert(cur-left,prev);cur-leftprev;if(prev){prev-rightcur;}prevcur;InorderConvert(cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prevnullptr;InorderConvert(pRootOfTree,prev);TreeNode* rootpRootOfTree;while(rootroot-left){rootroot-left;}return root;}
};
从前序与中序遍历序列构造二叉树 思路 将中序遍历的数组进行划区域处理ibegin,iend,iroot中序前序两个数组比较这进行。具体看代码。 class Solution {
public:TreeNode* _buildTree(vectorint preorder, vectorint inorder,int prei,int ibegin,int iend){if(ibeginiend){return nullptr;}TreeNode* rootnew TreeNode(preorder[prei]);int irootibegin;while(irootiend){if(preorder[prei]inorder[iroot]){break;}else{iroot;}}prei;root-left _buildTree(preorder,inorder,prei,ibegin,iroot-1);root-right _buildTree(preorder,inorder,prei,iroot1,iend);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int prei0;return _buildTree(preorder,inorder,prei,0,preorder.size()-1);}
};从中序与后序遍历序列构造二叉树 思路 该题和上一个题的思路是相同的就是将前序改为后序了所以就是prei改为从后开始遍历。 class Solution {
public:TreeNode* _buildTree(vectorint preorder, vectorint inorder,int prei,int ibegin,int iend){if(ibeginiend){return nullptr;}TreeNode* rootnew TreeNode(preorder[prei]);int irootibegin;while(irootiend){if(preorder[prei]inorder[iroot]){break;}else{iroot;}}prei--;root-right _buildTree(preorder,inorder,prei,iroot1,iend);root-left _buildTree(preorder,inorder,prei,ibegin,iroot-1);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int preipostorder.size()-1;return _buildTree(postorder,inorder,prei,0,postorder.size()-1);}
};二叉树的前序遍历非递归 思路 创建一个数组和一个找是将树的左子树先进行都先进入数组按顺序。并且将前面进入数组的节点放入栈当中之后进行对右子树的遍历这时要将指向右子树的这颗节点进行删除在栈当中。 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* s;TreeNode* curroot;while(cur || !s.empty()){while(cur){v.push_back(cur-val);s.push(cur);curcur-left;}TreeNode* tops.top();s.pop();curtop-right;}return v;}
};二叉树的中序遍历非递归 思路 它的思路是和上一道题的解法是相同的就是将pop出的节点挨个放入数组。 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* s;TreeNode* curroot;while(cur || !s.empty()){while(cur){s.push(cur);curcur-left;}TreeNode* tops.top();v.push_back(top-val);s.pop();curtop-right;}return v;}
};二叉树的后续遍历 思路 他与上述的问题差距就是如何让右子树在节点的前面输出而采用的方法就是创建一个变量用于判断是否右子树已经在父节点前面输出了。 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint v;stackTreeNode* s;TreeNode* curroot;TreeNode* prenullptr;while(cur || !s.empty()){while(cur){s.push(cur);curcur-left;}TreeNode* tops.top();if(top-rightnullptr || pretop-right){v.push_back(top-val);pretop;s.pop();}else{curtop-right;} }return v;}
};
