网站建设的推广渠道,网站建设的知名品牌,网上创建公司流程,crm客户管理系统api二叉树创建字符串 我们首先进行题目的解读#xff1a; 大概意思就是用#xff08;#xff09;把每个节点的值给括起来#xff0c;然后再经过一系列的省略的来得到最后的结果
大家仔细观察题目给出的列子就可以发现#xff0c;其实这个题目可以大致分为三种情况#xff1…二叉树创建字符串 我们首先进行题目的解读 大概意思就是用把每个节点的值给括起来然后再经过一系列的省略的来得到最后的结果
大家仔细观察题目给出的列子就可以发现其实这个题目可以大致分为三种情况
1 节点的左孩子和右孩子都在不能省略括号 2 节点没有左孩子只有右孩子不能省略括号 3 节点没有右孩子只有左孩子可以省略这个空节点的括号用来区分第二种情况保证了一个字符串只能对应一个二叉搜索树
就比如例1
例子中给出的初步转化的字符串是没有经过省略的其实4后面还要加上两个空括号才完美这里题目有一点小误差
就比如节点2他的右孩子节点是空的所以那个括号就要省略4和3的两个括号都省略就可以得到最后的结果了
代码如下 我们首先定义一个字符串如果根节点root为空就直接返回这个空字符串不为空先root内存储的val 如果root的左孩子节点或者root的右孩子节点不为空的话就要把root的左孩子节点的val用括号括起来就算左孩子为空这个括号也不能省略 如果root的右孩子不为空就要把root的右孩子用括号括起来最后 返回时str即可
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;}
};二叉树的分层遍历
正 这个题目是一个典型的vector里面套vector(int)的题目他最后返回的是双层结构 我们可以用到一个队列这个队列用来存放节点而双层的vector容器就用来存放层序遍历节点的val最后返回
我们先将root节点放进队列然后当他出来后将他的左右孩子节点放入队列只要队列不为空不就继续 完整代码如下
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode* q;vectorvectorint vv;if(rootnullptr)return vv;int levelsize0;q.push(root);levelsizeq.size();while(!q.empty()){vectorint v;while(levelsize--){TreeNode* nodeq.front();q.pop();v.push_back(node-val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}vv.push_back(v);levelsizeq.size();}return vv;}
};反 自底向上的层序遍历我们就偷懒直接用上面的代码用一个reverse函数反转即可
将vv的迭代器反转
class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode* q;vectorvectorint vv;if(rootnullptr)return vv;int levelsize0;q.push(root);levelsizeq.size();while(!q.empty()){vectorint v;while(levelsize--){TreeNode* nodeq.front();q.pop();v.push_back(node-val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}vv.push_back(v);levelsizeq.size();}reverse(vv.begin(),vv.end());return vv;}
};最近公共祖先 其实我们画图之后可以看到公共祖先节点有几个很明显的特征 如果一个节点在本节点的左子树另一个在本节点的右子树上那么这个节点就是那两个节点的公共祖先
如果两个节点都在一个节点的左或者右我们就用一个辅助函数来递归完成都在左边或者右边那么两个节点之中有一个一定时他们两个节点的公共祖先 完整代码如下
class Solution {
public:
//判断是否在这个树上
bool isintree(TreeNode* root,TreeNode* x)
{if(rootnullptr)return false;if(rootx)return true;return isintree(root-left,x)||isintree(root-right,x);
}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(rootp||rootq)return root;bool pinleftisintree(root-left,p);bool pinrightisintree(root-right,p);bool qinleftisintree(root-left,q);bool qinrightisintree(root-right,q);//一个在左一个在右if((pinleftqinright)||(pinrightqinleft))return root;//都在左if(pinleftqinleft)return lowestCommonAncestor(root-left,p,q);//都在右if(pinrightqinright)return lowestCommonAncestor(root-right,p,q);return nullptr;}
};二叉树搜索树转换成排序双向链表 我们观察可以看到最后排序出来的双向链表是一个有序的链表而二叉搜索树的中序遍历一定是一个有序的序列所以我们在这里要定义一个中序遍历的函数来用到解题
我们需要用到一个辅助的prev节点令cur的left为prev如果prev不为空就令prev的right为cur即可
class Solution {
public:void inorder(TreeNode* cur,TreeNode* prev){if(curnullptr)return;inorder(cur-left,prev);cur-leftprev;if(prev)prev-rightcur;prevcur;inorder(cur-right,prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prevnullptr;inorder(pRootOfTree,prev);TreeNode* headpRootOfTree;while(headhead-left){headhead-left;}return head;}
};前序中序还原二叉树 本题是根据前序和中序来构造二叉树我们知道前序的第一个节点就是二叉树的根节点而中序中根节点左边的就是左子树右边为右子树然后再遍历前序第二个节点再次带入中序前序的“根节点”能够将中序分为两个区间分为区间后我们再递归两个区间
完整代码如下
class Solution {
public:TreeNode* _buildTree(vectorint preorder,vectorint inorder,int prei,int begin,int end){if(beginend)return nullptr;TreeNode* rootnew TreeNode(preorder[prei]);int rootibegin;while(rootiend){if(inorder[rooti]preorder[prei])break;elserooti;}prei;root-left_buildTree(preorder,inorder,prei,begin,rooti-1);root-right_buildTree(preorder,inorder,prei,rooti1,end);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int i0;return _buildTree(preorder,inorder,i,0,inorder.size()-1);}
};中序和后序还原二叉树 中序和后续构造二叉树就和前序和后续构造一样转变一个思路 但是要注意由于后序是左右根所以要先递归右在递归左
class Solution {
public:TreeNode* _buildTree(vectorint inorder, vectorint postorder,int prei,int begin,int end){if(beginend)return nullptr;TreeNode* rootnew TreeNode(postorder[prei]);int rootibegin;while(rootiend){if(inorder[rooti]postorder[prei])break;elserooti;}prei--;root-right_buildTree(inorder,postorder,prei,rooti1,end);root-left_buildTree(inorder,postorder,prei,begin,rooti-1);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {int i postorder.size()-1;return _buildTree(inorder,postorder,i,0,inorder.size()-1);}
};
