网上那些彩票网站可以自己做吗,免费logo设计一键生成无水印,中国建筑信息资讯网,wordpress禁用ip第十五天#xff0c;二叉树part03#x1f4aa;#xff0c;编程语言#xff1a;C
目录
257.完全二叉树的节点个数
110.平衡二叉树
257.二叉树的所有路径
404.左叶子之和
总结 257.完全二叉树的节点个数 文档讲解#xff1a;代码随想录完全二叉树的节点个数 视频讲解…第十五天二叉树part03编程语言C
目录
257.完全二叉树的节点个数
110.平衡二叉树
257.二叉树的所有路径
404.左叶子之和
总结 257.完全二叉树的节点个数 文档讲解代码随想录完全二叉树的节点个数 视频讲解手撕完全二叉树的节点个数 题目 学习
1. 根据完全二叉树的定义我们可以把二叉树分为一个个满二叉树。满二叉树的定义为除叶子节点外其余节点均含有左右两个孩子此时节点的个数为2^height - 1height就是这个满二叉树的高度。
2. 那如何确定是否是满二叉树呢本题我们可以借助完全二叉树的定义由于完全二叉树的特点一个节点一定会先有它的左孩子再有它的右孩子。因此倘若一棵树的一直往左遍历的深度与一直往右遍历的深度相同则说明这是一颗满二叉树因为中间的节点一定是填满的否则往右的深度一定时小于往左的深度。
3. 确定以上两点后如何把一个二叉树分为一个个满二叉树。本题我们可以采用后序遍历的方法在向下移动的过程中我们可以每次判断该节点是否为一棵满二叉树的根节点采用的方式就是2中所说的判断向左和向右的深度是否一样如果是则可以通过满二叉树的式子直接返回该树的节点数如果不是则继续往下。注意叶子节点在这也被我们看作成了一颗满二叉树高度为1节点个数为1。
代码
//时间复杂度O(logn*logn)
//空间复杂度O(logn)
class Solution {
public:int countNodes(TreeNode* root) {//根节点为空返回0//终止条件if (root nullptr) return 0;TreeNode* left root-left;TreeNode* right root-right;int leftheight 0; int rightheight 0;while(left) {leftheight;left left-left;}while(right) {rightheight;right right-right;}//如果两边深度一样则说明是一个完全二叉树完全二叉树的节点数量为2^(leftheight 1) - 1 if (leftheight rightheight) return (2 leftheight) - 1;//不满足终止条件的话进入递归循环int leftnum countNodes(root-left); //遍历左子树int rightnum countNodes(root-right); //遍历右子树return 1 leftnum rightnum;}
};
注意本题也可以采用普通二叉树求节点数量的方式采用层次遍历时间复杂度为O(n)。 110.平衡二叉树 文档讲解代码随想录平衡二叉树 视频讲解手撕平衡二叉树 题目 学习平衡二叉树指的是任意一个节点的左右子树的高度差不大于1。依据这个特点我们可以采取后序遍历的方式遍历每一个子树的高度并且当存在一个子树的高度差大于2时就可以立刻返回-1不用继续遍历下去。
代码
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public://1.确定返回值参数列表。//返回值由于递归过程中需要比较左右子树的高度所有返回值应该为int//参数比较根节点左右子树的高度因此只需要传入根节点即可int Height(TreeNode* root) {//2.确定终止条件、单层递归逻辑//①如果根节点为空返回长度为0if (root nullptr) return 0;//②如果已得知左子树不平衡,返回-1int leftheight Height(root-left);if (leftheight -1) return -1;//③如果已得知右子树不平衡返回-1int rightheight Height(root-right);if (rightheight -1) return -1;return abs(leftheight - rightheight) 1 ? -1 : (1 max(leftheight, rightheight));} bool isBalanced(TreeNode* root) {if (Height(root) -1) return false;return true;}
};
注意
此题不适合使用前序遍历前序遍历一般用于求树的深度是自顶向下的过程。 因此每次比较一个子树的深度时都需要遍历所有的子节点时间复杂度会达到O(n^2)。后序遍历则不同是自底向上的过程在遍历的过程中从底部开始比较并把比较的结果不断往上传递因此只需要遍历一遍节点即可。此题也不适合使用迭代的方式本题存在回溯比较的过程使用迭代法会使得代码很复杂且不利于实现回溯的过程虽然递归一般来说都能用迭代来实现但是也需要分析使用的场景。 257.二叉树的所有路径 文档讲解二叉树的所有路径 视频讲解手撕二叉树的所有路径 题目 学习
1. 本题要找到所有路径因此必定需要遍历所有的节点同时每条路径都是从根节点开始的因此显然本题适合采用前序遍历来进行节点的遍历遍历到下一个节点的时候其父节点的信息就已经载入。
2. 同时本题存在大量的回溯过程即找到一条路径后要回到一个拐点中间节点再去寻找另一条路路径。回溯是下一章节的重点内容其主要的实现方式就是递归实现因此本题采用前序遍历的递归形式。
3. 本题在递归上有两个主要注意的点①本题终止条件不再是找到空节点而是找到叶子节点这条路径就可以终止了②本题采用前序遍历但是对节点的处理要放在终止条件判断前因为每遍历到一个节点就需要把它加入到字符串当中。
代码
//时间复杂度O(n^2)
//空间复杂度O(n^2)
class Solution {
public://注意path不能使用引用的方式这种赋值的方式不会改变传进来的值因此会实现自动回溯void traversal(TreeNode* cur, string path, vectorstring result) {path to_string(cur-val); // 中中为什么写在这里因为最后一个节点也要加入到path中path -;if(cur-left nullptr cur-right nullptr) {//把最后多余的箭头pop()掉path.pop_back();path.pop_back();result.push_back(path);}if(cur-left) { //左traversal(cur-left, path, result);}if(cur-right) { //右traversal(cur-right, path, result);}}vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;traversal(root, , result);return result;}
};
注意上面是使用了拷贝构造string path的方式每一个递归拷贝了自己的一份path以此来实现回溯过程。但也能够使用引用的方式大家公用一份数组但要注意此时需要自己进行回溯。
class Solution {
private:void traversal(TreeNode* cur, vectorint path, vectorstring result) {path.push_back(cur-val); // 中中为什么写在这里因为最后一个节点也要加入到path中 // 这才到了叶子节点if (cur-left NULL cur-right NULL) {string sPath;for (int i 0; i path.size() - 1; i) {sPath to_string(path[i]);sPath -;}sPath to_string(path[path.size() - 1]);result.push_back(sPath);return;}if (cur-left) { // 左 traversal(cur-left, path, result);path.pop_back(); // 回溯}if (cur-right) { // 右traversal(cur-right, path, result);path.pop_back(); // 回溯}}public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;vectorint path;if (root NULL) return result;traversal(root, path, result);return result;}
};
总结回溯的过程实际上就是把上一个循环的所有数据环境保存下来再回到上一个循环的时候保证环境不变的过程。可以通过把递归放入栈中体会回溯。 404.左叶子之和 文档讲解代码随想录左叶子之和 视频讲解手撕左叶子之和 题目 学习本题需要找到所有的左叶子节点。左叶子节点的特点1.是叶子节点2.是父节点的左孩子。根据这两个特点来进行递归构造。
代码前序遍历递归
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:// 1.确定返回值和参数列表这里我们使用一个sum来计算总和因此不需要返回值。void sumLeft(int sum, TreeNode* root) {//左叶子节点的定义1.是父节点的左节点2.是叶子节点//2.确定终止条件if(root nullptr) return;//其实这个也可以不写如果不写不影响结果但就会让递归多进行了一层。if(root-left nullptr root-right nullptr) return;//3.确定单层递归逻辑//找到左叶子节点的父节点if(root-left ! nullptr root-left-left nullptr root-left-right nullptr) {sum root-left-val;}//如果没找到左叶子节点的父节点则向下遍历sumLeft(sum, root-left);sumLeft(sum, root-right);}int sumOfLeftLeaves(TreeNode* root) {int sum 0;sumLeft(sum, root);return sum;}
};
注意本题也可以采用后序遍历的方式。采用后序的遍历返回值设为int型从底部开始把左叶子节点的值累加并传递给父节点。
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root NULL) return 0;if (root-left NULL root-right NULL) return 0;int leftValue sumOfLeftLeaves(root-left); // 左if (root-left !root-left-left !root-left-right) { // 左子树就是一个左叶子的情况leftValue root-left-val;}int rightValue sumOfLeftLeaves(root-right); // 右int sum leftValue rightValue; // 中return sum;}
};总结
今天的题重在对递归的使用和对递归三大条件的设计上。
完全二叉树的节点个数通过对递归条件终止条件的特殊处理讲时间复杂度下降。平衡二叉树重点在于后序遍历求得树的高度前序遍历求得树的深度要根据需求进行选择。二叉树的所有路径重点在于对回溯的理解要找到所有的路径需要保存父节点的信息。同时由于每个节点遍历的时候就需要立马加入路径队列因此还需要把对节点的处理放在终止条件的判断前。左叶子之和有两种不同的方法根据左叶子节点的特点构造递归三部曲。 文章转载自： http://www.morning.ryspp.cn.gov.cn.ryspp.cn http://www.morning.dgwrz.cn.gov.cn.dgwrz.cn http://www.morning.ymjgx.cn.gov.cn.ymjgx.cn http://www.morning.nzsdr.cn.gov.cn.nzsdr.cn http://www.morning.xblrq.cn.gov.cn.xblrq.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.rlbc.cn.gov.cn.rlbc.cn http://www.morning.dlrsjc.com.gov.cn.dlrsjc.com http://www.morning.qcfcz.cn.gov.cn.qcfcz.cn http://www.morning.kgrwh.cn.gov.cn.kgrwh.cn http://www.morning.zcnwg.cn.gov.cn.zcnwg.cn http://www.morning.ykrkq.cn.gov.cn.ykrkq.cn http://www.morning.pqkgb.cn.gov.cn.pqkgb.cn http://www.morning.wjtwn.cn.gov.cn.wjtwn.cn http://www.morning.mrfbp.cn.gov.cn.mrfbp.cn http://www.morning.kfmlf.cn.gov.cn.kfmlf.cn http://www.morning.qpxrr.cn.gov.cn.qpxrr.cn http://www.morning.xstfp.cn.gov.cn.xstfp.cn http://www.morning.nfcxq.cn.gov.cn.nfcxq.cn http://www.morning.gzttoyp.com.gov.cn.gzttoyp.com http://www.morning.bkkgt.cn.gov.cn.bkkgt.cn http://www.morning.wrlqr.cn.gov.cn.wrlqr.cn http://www.morning.prmbb.cn.gov.cn.prmbb.cn http://www.morning.ngjpt.cn.gov.cn.ngjpt.cn http://www.morning.wwklf.cn.gov.cn.wwklf.cn http://www.morning.gjqgz.cn.gov.cn.gjqgz.cn http://www.morning.pgkpt.cn.gov.cn.pgkpt.cn http://www.morning.nfzw.cn.gov.cn.nfzw.cn http://www.morning.rqmr.cn.gov.cn.rqmr.cn http://www.morning.lfbzg.cn.gov.cn.lfbzg.cn http://www.morning.lnrhk.cn.gov.cn.lnrhk.cn http://www.morning.tbnpn.cn.gov.cn.tbnpn.cn http://www.morning.jrpmf.cn.gov.cn.jrpmf.cn http://www.morning.rcwbc.cn.gov.cn.rcwbc.cn http://www.morning.xwlmg.cn.gov.cn.xwlmg.cn http://www.morning.kxymr.cn.gov.cn.kxymr.cn http://www.morning.ltrms.cn.gov.cn.ltrms.cn http://www.morning.zwhtr.cn.gov.cn.zwhtr.cn http://www.morning.bxhch.cn.gov.cn.bxhch.cn http://www.morning.ksgjn.cn.gov.cn.ksgjn.cn http://www.morning.ndhxn.cn.gov.cn.ndhxn.cn http://www.morning.rwpfb.cn.gov.cn.rwpfb.cn http://www.morning.tsflw.cn.gov.cn.tsflw.cn http://www.morning.xnnpy.cn.gov.cn.xnnpy.cn http://www.morning.lqznq.cn.gov.cn.lqznq.cn http://www.morning.spwln.cn.gov.cn.spwln.cn http://www.morning.c7513.cn.gov.cn.c7513.cn http://www.morning.xtrzh.cn.gov.cn.xtrzh.cn http://www.morning.rlqwz.cn.gov.cn.rlqwz.cn http://www.morning.rxcqt.cn.gov.cn.rxcqt.cn http://www.morning.fgtls.cn.gov.cn.fgtls.cn http://www.morning.rhkgz.cn.gov.cn.rhkgz.cn http://www.morning.xxhc.cn.gov.cn.xxhc.cn http://www.morning.mumgou.com.gov.cn.mumgou.com http://www.morning.ie-comm.com.gov.cn.ie-comm.com http://www.morning.gjqnn.cn.gov.cn.gjqnn.cn http://www.morning.cbpmq.cn.gov.cn.cbpmq.cn http://www.morning.yxdrf.cn.gov.cn.yxdrf.cn http://www.morning.pdynk.cn.gov.cn.pdynk.cn http://www.morning.fxzlg.cn.gov.cn.fxzlg.cn http://www.morning.bpmdh.cn.gov.cn.bpmdh.cn http://www.morning.gzzncl.cn.gov.cn.gzzncl.cn http://www.morning.trffl.cn.gov.cn.trffl.cn http://www.morning.lmctj.cn.gov.cn.lmctj.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.pmftz.cn.gov.cn.pmftz.cn http://www.morning.csnmd.cn.gov.cn.csnmd.cn http://www.morning.tbbxn.cn.gov.cn.tbbxn.cn http://www.morning.drnfc.cn.gov.cn.drnfc.cn http://www.morning.znpyw.cn.gov.cn.znpyw.cn http://www.morning.qlxgc.cn.gov.cn.qlxgc.cn http://www.morning.kgkph.cn.gov.cn.kgkph.cn http://www.morning.ppqzb.cn.gov.cn.ppqzb.cn http://www.morning.hkpn.cn.gov.cn.hkpn.cn http://www.morning.pxbrg.cn.gov.cn.pxbrg.cn http://www.morning.qwdlj.cn.gov.cn.qwdlj.cn http://www.morning.mzhgf.cn.gov.cn.mzhgf.cn http://www.morning.qbnfc.cn.gov.cn.qbnfc.cn http://www.morning.ghyfm.cn.gov.cn.ghyfm.cn http://www.morning.zfhwm.cn.gov.cn.zfhwm.cn
