《代码随想录》刷题打卡day11：二叉树part01

文章目录1. 二叉树基础理论2. 题目打卡DFS:144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历递归法迭代法统一迭代法BFS102.二叉树的层序遍历107.二叉树的层次遍历199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度1. 二叉树基础理论二叉树种类满二叉树、完全二叉树仅底层节点未填满未填满的话节点必须在左边二叉搜索树值左中右、平衡二叉搜索树左右子树深度差不超过1二叉树存储方式链式存储顺序存储链式存储图顺序存储图二叉树的遍历方式深度优先遍历前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法广度优先遍历层次遍历迭代法二叉树的定义structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};2. 题目打卡DFS:144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历递归法递归算法的三个要素。每次写递归都按照这三要素来写可以保证大家写出正确的递归算法确定递归函数的参数和返回值确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。确定单层递归的逻辑确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。classSolution{//前序遍历public:voidtraversal(TreeNode*cur,vectorintvec){if(curNULL)return;vec.push_back(cur-val);// 中traversal(cur-left,vec);// 左traversal(cur-right,vec);// 右}vectorintpreorderTraversal(TreeNode*root){vectorintresult;traversal(root,result);returnresult;}};迭代法前序遍历:是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。为什么要先加入 右孩子再加入左孩子呢 因为这样出栈的时候才是中左右的顺序。classSolution{public:vectorintpreorderTraversal(TreeNode*root){stackTreeNode*st;vectorintresult;if(rootNULL)returnresult;st.push(root);while(!st.empty()){TreeNode*nodest.top();// 中st.pop();result.push_back(node-val);if(node-right)st.push(node-right);// 右空节点不入栈if(node-left)st.push(node-left);// 左空节点不入栈}returnresult;}};中序遍历为了解释清楚我说明一下 刚刚在迭代的过程中其实我们有两个操作处理将元素放进result数组中访问遍历节点分析一下为什么刚刚写的前序遍历的代码不能和中序遍历通用呢因为前序遍历的顺序是中左右先访问的元素是中间节点要处理的元素也是中间节点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间节点。那么再看看中序遍历中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。classSolution{public:vectorintinorderTraversal(TreeNode*root){vectorintresult;stackTreeNode*st;TreeNode*curroot;while(cur!NULL||!st.empty()){if(cur!NULL){// 指针来访问节点访问到最底层st.push(cur);// 将访问的节点放进栈curcur-left;// 左}else{curst.top();// 从栈里弹出的数据就是要处理的数据放进result数组里的数据st.pop();result.push_back(cur-val);// 中curcur-right;// 右}}returnresult;}};后序遍历再来看后序遍历先序遍历是中左右后序遍历是左右中那么我们只需要调整一下先序遍历的代码顺序就变成中右左的遍历顺序然后在反转result数组输出的结果顺序就是左右中了。统一迭代法就是要处理的节点放入栈之后紧接着放入一个空指针作为标记。这种方法可以叫做空指针标记法。classSolution{//中序遍历public:vectorintinorderTraversal(TreeNode*root){vectorintresult;stackTreeNode*st;if(root!NULL)st.push(root);while(!st.empty()){TreeNode*nodest.top();if(node!NULL){st.pop();// 将该节点弹出避免重复操作下面再将右中左节点添加到栈中if(node-right)st.push(node-right);// 添加右节点空节点不入栈st.push(node);// 添加中节点st.push(NULL);// 中节点访问过但是还没有处理加入空节点做为标记。if(node-left)st.push(node-left);// 添加左节点空节点不入栈}else{// 只有遇到空节点的时候才将下一个节点放进结果集st.pop();// 将空节点弹出nodest.top();// 重新取出栈中元素st.pop();result.push_back(node-val);// 加入到结果集}}returnresult;}};BFSclassSolution{public:vectorvectorintlevelOrder(TreeNode*root){queueTreeNode*que;if(root!NULL)que.push(root);vectorvectorintresult;while(!que.empty()){intsizeque.size();vectorintvec;// 这里一定要使用固定大小size不要使用que.size()因为que.size是不断变化的for(inti0;isize;i){TreeNode*nodeque.front();que.pop();vec.push_back(node-val);if(node-left)que.push(node-left);if(node-right)que.push(node-right);}result.push_back(vec);}returnresult;}};102.二叉树的层序遍历107.二叉树的层次遍历199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度