【C++进阶加餐】加餐来啦！二叉树进阶算法题

根据二叉树创建字符串左为空右边不为空则不能省略()其余情况可以省略/** * 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) {} * }; */classSolution{public:stringtree2str(TreeNode*root){string str;if(rootnullptr)returnstr;//前序遍历strto_string(root-val);//左边不为空要加括号//左边为空右边不为空也要加括号if(root-left||root-right){str(;strtree2str(root-left);str);}//右边不为空要加括号if(root-right){str(;strtree2str(root-right);str);}returnstr;}};二叉树的分层遍历1/** * 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) {} * }; */classSolution{public:vectorvectorintlevelOrder(TreeNode*root){vectorvectorintvv;queueTreeNode*q;intlevelsize0;if(root){q.push(root);levelsize1;}while(!q.empty()){vectorintv;//一层节点全部出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);}}//一层出完先存进vvvv.push_back(v);levelsizeq.size();}returnvv;}};给定一个二叉树, 找到该树中两个指定节点的最近公共祖先最近的公共祖先一个节点在左一个节点在右/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:boolIsInTree(TreeNode*root,TreeNode*node){if(rootnullptr)returnfalse;if(rootnode)returntrue;returnIsInTree(root-left,node)||IsInTree(root-right,node);}TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(rootnullptr)returnnullptr;if(rootp||rootq)returnroot;boolpInLeftIsInTree(root-left,p);boolqInLeftIsInTree(root-left,q);// 一个在左一个在右if(pInLeft!qInLeft)// 等价于 (pInLeft !qInLeft) || (!pInLeft qInLeft)returnroot;// 两个都在左子树if(pInLeftqInLeft)returnlowestCommonAncestor(root-left,p,q);// 两个都在右子树elsereturnlowestCommonAncestor(root-right,p,q);}};二叉树搜索树转换成排序双向链表思路一中序遍历搜索二叉树遍历顺序是有序的将二叉树的节点指针放到一个vector中再把前后节点的链接关系进行修改空间复杂度O(N)思路2依旧中序遍历搜索二叉树遍历顺序是有序的遍历过程中修改左指针为前驱和右指针为后继指针。记录一个 cur 和 prev , cur 为当前中序遍历到的结点 prev 为上一个中序遍历的结点 cur - left 指向 prev , cur - right 无法指向中序下一个因为不知道中序下一个是谁但是 prev - right 指向 cur ;一个结点时修改指向后继的。也就是说每个结点的左是在中遍历到当前结点时修改指向前驱的但是当前结点的右是在遍历到下一个节点时修改指向后继的/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/classSolution{public://prev必须要用引用传参否则不会改变实参voidInorderConvert(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*root){TreeNode*prevnullptr;//空返回空链表if(rootnullptr)returnnullptr;InorderConvert(root,prev);//先等于根节点向左递归直到找到头结点TreeNode*headroot;while(head-left){headhead-left;}//循环链表下面两句代码根据题目要求可删减//如果没要求循环就删除head-leftprev;prev-righthead;returnhead;}};根据二叉树的前序和中序遍历结果还原该二叉树classSolution{public://prei要改变所以要引用TreeNode*build(vectorintpreorder,vectorintinorder,intprei,intinbegin,intinend){if(inbegininend)returnnullptr;//前序确定根TreeNode*rootnewTreeNode(preorder[prei]);//中序分割左右子树introotiinbegin;while(rootiinend){if(preorder[prei]inorder[rooti])break;elserooti;}prei;//找到根//[inbegin1,rooti-1],rooti,[rooti1,inend]root-leftbuild(preorder,inorder,prei,inbegin,rooti-1);root-rightbuild(preorder,inorder,prei,rooti1,inend);returnroot;}TreeNode*buildTree(vectorintpreorder,vectorintinorder){inti0;returnbuild(preorder,inorder,i,0,inorder.size()-1);}};根据二叉树的中序和后序遍历结果还原该二叉树classSolution{public:TreeNode*build(vectorintpostorder,vectorintinorder,intpost_idx,intin_begin,intin_end){if(in_beginin_end)returnnullptr;TreeNode*rootnewTreeNode(postorder[post_idx]);introotiin_begin;while(rootiin_end){if(inorder[rooti]postorder[post_idx]){break;}else{rooti;}}post_idx--;//后序遍历是左右根//所以先右再左root-rightbuild(postorder,inorder,post_idx,rooti1,in_end);root-leftbuild(postorder,inorder,post_idx,in_begin,rooti-1);returnroot;}TreeNode*buildTree(vectorintinorder,vectorintpostorder){intpost_idxpostorder.size()-1;returnbuild(postorder,inorder,post_idx,0,inorder.size()-1);}};