家居用品东莞网站建设,了解网页制作的基本知识,做网站切片,html中文模板本文#xff0c;我们主要讲解一些适合用C的数据结构来求解的二叉树问题#xff0c;其中涉及了二叉树的遍历#xff0c;栈和队列等数据结构#xff0c;递归与回溯等知识#xff0c;希望可以帮助你进一步理解二叉树。 目录
1.二叉树的层序遍历
2.二叉树的公… 本文我们主要讲解一些适合用C的数据结构来求解的二叉树问题其中涉及了二叉树的遍历栈和队列等数据结构递归与回溯等知识希望可以帮助你进一步理解二叉树。 目录
1.二叉树的层序遍历
2.二叉树的公共祖先
3.二叉搜索树与双向链表
4.二叉树的创建(前序中序后序中序)
前序中序
中序后序
5.二叉树的三种迭代法遍历 1.二叉树的层序遍历
题目链接二叉树的层序遍历
思路分析 这个题目的难点是如何控制层序遍历的同时还能保持入队操作我们知道二叉树的的层序遍历一般和队列联系在一起使用包括一些bfs的习题也经常以队列、栈作为遍历的容器本题我们需要思考如何能够遍历某一层的同时将该层的下一层的节点保存下来同时还需要将该层的节点按从左到右的顺序输出显然我们需要将每一层的节点聚在一起保存这样才能保证输出的正确性我们可以提供一个输出的变量len表示该层需要输出几个节点然后将该层的节点输出的同时把它的左右孩子都入队这样一来就能保证每一层的节点都聚在一起并且按从左到右的顺序排列之后保存输出即可。
AC代码
class Solution {
public:queueTreeNode* q;vectorvectorint ans;vectorvectorint levelOrder(TreeNode* root) {if(!root)return ans;vectorint cot;q.push(root);int len1;while(!q.empty()){while(len--){TreeNode* tmpq.front();q.pop();if(tmp-left!nullptr) q.push(tmp-left);if(tmp-right!nullptr) q.push(tmp-right);cot.push_back(tmp-val);}lenq.size();ans.push_back(cot);cot.clear();} return ans;}
};
2.二叉树的公共祖先
题目链接二叉树的公共祖先
思路分析 难点在于如何在找到两个节点的条件下回溯双方的祖先节点来确定最近公共祖先这里仅提供其中一个思路我们可以保存寻找路径然后让两个路径中较长的路径也就是离公共祖先节点较远的逐渐向上走直到两条路径交合交合点就是最近公共祖先。
class Solution {
public:bool isexist(TreeNode*root,TreeNode *key){if(rootnullptr)return false;else if(rootkey)return true;elsereturn isexist(root-left,key)||isexist(root-right,key);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stackTreeNode*ppath;stackTreeNode*qpath;TreeNode*curroot;ppath.push(root);qpath.push(root);//寻找p的路径while(cur){if(curp)break;else if(isexist(cur-left,p)) {ppath.push(cur-left);curcur-left;}else if(isexist(cur-right,p)){ppath.push(cur-right);curcur-right;}}//寻找q的路径curroot;while(cur){if(curq)break;else if(isexist(cur-left,q)) {qpath.push(cur-left);curcur-left;}else if(isexist(cur-right,q)){qpath.push(cur-right);curcur-right;}}//开始寻找TreeNode *ansnullptr;while(ppath.size()qpath.size()){if(ppath.size() qpath.size())ppath.pop();else if(ppath.size() qpath.size())qpath.pop();else if(ppath.size() qpath.size()){if(ppath.top()qpath.top()){ansppath.top();break;}else{ppath.pop();qpath.pop();}}}return ans;}
};
3.二叉搜索树与双向链表
题目链接二叉搜索树与双向链表
思路分析 本体的难点在于如何在原树上做修改而不影响接下来的操作当然暴力也可以做但是这里要求我们在原树上直接做修改所以这里不解释暴力做法我们就按题目规定的思路来我们知道二叉搜索树最左端的元素一定最小最右端的元素一定最大因此二叉搜索树的中序遍历就是一个递增序列我们只要对它中序遍历就可以组装成为递增双向链表。 我们可以使用一个指针pre指向当前结点root的前继。例如root为指向10的时候preNode指向8对于当前结点root有root-left要指向前继pre中序遍历时对于当前结点root其左孩子已经遍历完成了此时root-left可以被修改。同时pr-right要指向当前结点当前结点是pre的后继此时对于pre结点它已经完全加入双向链表。 class Solution {
public:TreeNode *headnullptr;TreeNode*prenullptr;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTreenullptr)return nullptr;Convert(pRootOfTree-left);//找到最左节点也就是最小的那个点if(headnullptr)//此时是第一个最小值也就是头结点{headpRootOfTree;prepRootOfTree;}else{pre-rightpRootOfTree;pRootOfTree-leftpre;prepRootOfTree;}Convert(pRootOfTree-right);return head;}
};4.二叉树的创建(前序中序后序中序) 这应该算是一个老生常谈的问题了算是经典中的经典了其实不论是前序中序还是后序中序其原理都大同小异所以我们将这两个例子放在一起讲解有助于理解和记忆。
题目链接105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode 106. 从中序与后序遍历序列构造二叉树 - 力扣LeetCode
思路分析
前序中序
递归法 只要我们在中序遍历中定位到根节点那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的因此我们就可以对应到前序遍历的结果中也就是每次都从中序遍历中寻找根节点然后通过中序遍历将左右子树划分开来再递归构造新的左右子树即可
class Solution {
public:TreeNode *rootnullptr;TreeNode* build(vectorint pre, vectorint in,int pl,int pr,int il,int ir){if(plpr)//如果越界直接返回空即可return nullptr;TreeNode* curnew TreeNode(pre[pl]);//前序遍历第一个元素一定是某棵子树的根节点int idx0,len0;//分别表示根节点在中序遍历的位置和左子树的节点个数for(int iil;iir;i){if(in[i]pre[pl]) //找到根节点所在的中序遍历的位置以确定根的左右子树{idxi;leni-il;//找到对应的左子树的节点个数break;}}cur-leftbuild(pre,in,pl1,pllen,il,idx-1);cur-rightbuild(pre,in,pl1len,pr,idx1,ir);return cur;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {root build(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);return root;}
};
迭代法 我们先来假设一种极端情况如果一棵二叉树只有左孩子那么其结构就类似于一张单链表它的前序遍历和中序遍历一定就相反我们将这个由此就可以判断此之前的过程中的每一个节点都没有右孩子为了便于理解我们用例子加以说明 那么此时我们就可以维护一个栈用来保存还没有考虑过右孩子的节点按前序遍历的序列一直向二叉树的左端去遍历当某个时刻遍历到了二叉树的最左节点此时说明前序遍历的下一个元素一定是栈中某个节点的右孩子了然后我们再依次对比栈中元素和中序序列取出栈中的最后一个满足前序和中序序列相反的元素将新加入的节点加入其右孩子再将其入栈我们无需再考虑已经出栈的元素因为他们的右子树都已经被考虑完了所以其树结构已经形成了重复该过程直到前序序列遍历完毕即可形成一棵完整的树。
class Solution {
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {if(!preorder.size())return nullptr;TreeNode *rootnew TreeNode(preorder[0]);//先序遍历的第一个节点一定是根stackTreeNode*st;st.push(root);int idx0;//初始idx指向中序遍历的第一个元素整棵二叉树的最左节点for(int i1;ipreorder.size();i)//根节点已经加入所以前序遍历从下标1开始即可{TreeNode* nodest.top();if(node-val!inorder[idx])//如果加入节点还没判断是不是有右孩子{node-leftnew TreeNode(preorder[i]);st.push(node-left);//节点入栈等待判断}else //此时说明已经到达了某棵子树的最左节点,开始判断新加入的节点preorder[i])是哪一个栈中节点的右孩子{TreeNode* parentnullptr;while(!st.empty() st.top()-valinorder[idx]) //前中序遍历序列一致此时该节点没有右孩子{parentst.top();//最后一个出栈的节点一定是那个父节点用于保存上次出栈记录st.pop();idx;}parent-rightnew TreeNode(preorder[i]);//创建其右孩子st.push(parent-right);//不能忘了将新创建的节点加入因为该节点可能还有左右子树需要创建}}return root;}
};
中序后序
递归法 后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标然后根据其将中序遍历的数组分成左右两部分左边部分即左子树右边部分为右子树针对每个部分可以用同样的方法继续递归下去构造。
class Solution {
public:TreeNode*build(vectorint in, vectorint pos,int il,int ir,int pl,int pr){if(plpr)return nullptr;TreeNode*rootnew TreeNode(pos[pr]);//后序遍历的最后一个节点一定是根节点int idx0,len0;for(int iil;iir;i){if(pos[pr]in[i]){idxi;leni-il;break;}}root-leftbuild(in,pos,il,idx-1,pl,pllen-1);root-rightbuild(in,pos,idx1,ir,pllen,pr-1);return root;}TreeNode* buildTree(vectorint inorder, vectorint postorder) {return build(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);}
};
迭代法 此处和前中序创建的方法大同小异我们只需要注意前序和后序的区别即可因为后序遍历中和根节点挨在一块的是右子树所以我们转变一下思路可以通过构建右子树的过程中插入左节点来实现其余的原理均和前中序的原理类似。
class Solution {
public:TreeNode* buildTree(vectorint inorder, vectorint postorder) {if(!postorder.size())return nullptr;stackTreeNode*st;TreeNode* rootnew TreeNode(postorder[postorder.size()-1]);st.push(root);int idxpostorder.size()-1;for(int ipostorder.size() - 2;i0;i--){TreeNode* nodest.top();if(node-val!inorder[idx])//这次是县创建右子树{node-rightnew TreeNode(postorder[i]);st.push(node-right);}else//找到了第一个左孩子节点{TreeNode* parentnullptr;while(!st.empty()st.top()-valinorder[idx]){parentst.top();st.pop();--idx;}parent-leftnew TreeNode(postorder[i]);st.push(parent-left);}}return root;}
};
5.二叉树的三种迭代法遍历
题目链接二叉树的前序遍历、二叉树的中序遍历、二叉树的后序遍历
思路分析
前序遍历 对于前序遍历根左右的形式根节点一定是最先输出的难点在于如何转换方向也就是当遍历到左子树最后一个节点时如何将其转换为右子树再进行输出此时我们可以设置一个指针cur初始时cur一直向着左子树走当左子树遍历到最左节点时我们可以将当前的cur更新其父节点的右孩子节点然后cur再次往左走走到叶节点再次转向右子树重复递归这个过程即可。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint ans;stackTreeNode* st;TreeNode*curroot;while(cur || !st.empty()){while(cur){ans.push_back(cur-val);//将每棵子树的根节点直接加入st.push(cur);curcur-left;//接着寻找最左节点}//此时节点已经找到了最左节点curst.top()-right;//转而进入最左节点的右子树st.pop();//删除最左节点 }return ans;}
};
中序遍历 和前序遍历的大同小异此时我们的输出模式变成了左根右那么此时我们循环找到最左节点的时候就需要先输出最左节点在回溯找到根节点输出然后再递归到右子树进行输出即可。
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint ans;stackTreeNode* st;if(!root)return ans;TreeNode* curroot;while(cur||!st.empty()){while(cur){st.push(cur);//将左子树根节点入栈curcur-left;//向左查找最左节点}//此时cur已经是该子树上的最左节点TreeNode* pst.top();st.pop();ans.push_back(p-val);curp-right; //无论最左节点是否有右子树我们转换为右子树的子问题此时cur如果为空可直接回溯到最左节点的父节点进行操作}return ans;}
};
后序遍历 后序遍历与上面的两种方式有着些许不同其中后序遍历的难点是如何判断当前的节点能否作为根输出也就相当于如果左节点存在右子树且还没有输出那么我们就需要先考虑右子树的输出而不能先输出左节点反之如果其没有右子树或者右子树已经输出完了那么就可以直接输出所以每个左节点都需要进行特殊分析由于我们知道后序遍历的形式是左右根那么每个子树输出的最后个一定是其根节点而如果一个左节点有右子树那么此时其后序遍历的输出在左节点之前的节点一定是其右孩子节点我们可以以这个条件作为其右子树是否输出完毕的条件设置一个指针pre指向上一个被访问的节点此时就有两种情况 1.当前节点的右子树为空或者当前节点的右子树是上一个被访问的节点此时说明该节点作为根节点其右子树的输出已经完毕可以输出根节点了(注意此时要更新pre指针 2.如果右树存在且没有被访问那么就需要转到右树上去继续输出此时根节点不能删除。 class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint ans;stackTreeNode* st;TreeNode* curroot;TreeNode* prenullptr;while(cur || !st.empty()){while(cur){st.push(cur);curcur-left;}//此时已经到达了最左节点TreeNode* topst.top();if(top-rightnullptr || top-rightpre) //如果此时最左节点的右子树为空或者右子树已经被访问直接输出该左节点即可{st.pop();ans.push_back(top-val); pretop;//更新上次访问的节点}else{curtop-right;//先访问其右子树再输出根} }return ans;}
}; 后面有好的题目会继续补充敬请期待......
