建建设网站公司,电商运营的基本流程,企业信息网站,沧州 中企动力提供网站建设9.二叉树的最大深度
递归法
后序遍历
本题可以使用前序#xff08;中左右#xff09;#xff0c;也可以使用后序遍历#xff08;左右中#xff09;#xff0c;使用前序求的就是深度#xff0c;使用后序求的是高度。
二叉树节点的深度#xff1a;指从根节点到该节点…9.二叉树的最大深度
递归法
后序遍历
本题可以使用前序中左右也可以使用后序遍历左右中使用前序求的就是深度使用后序求的是高度。
二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数或者节点数取决于高度从0开始还是从1开始
而根节点的高度就是二叉树的最大深度所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
用后序遍历左右中来计算树的高度
1.确定递归函数的参数和返回值参数就是传入树的根节点返回就返回这棵树的深度所以返回值为int类型。
int getdepth(TreeNode* node)2.确定终止条件如果为空节点的话就返回0表示高度为0。
if (node NULL) return 0;3.确定单层递归的逻辑先求它的左子树的深度再求右子树的深度最后取左右深度最大的数值 再1 加1是因为算上当前中间节点就是目前节点为根节点的树的深度。
class solution {
public:int getdepth(TreeNode* node) {if (node NULL) return 0;int leftdepth getdepth(node-left); // 左int rightdepth getdepth(node-right); // 右int depth 1 max(leftdepth, rightdepth); // 中return depth;}int maxDepth(TreeNode* root) {return getdepth(root);}
};前序遍历
充分表现出求深度回溯的过程
class solution {
public:int result;void getdepth(TreeNode* node, int depth) {result depth result ? depth : result; // 中if (node-left NULL node-right NULL) return ;if (node-left) { // 左depth; // 深度1getdepth(node-left, depth);depth--; // 回溯深度-1 }if (node-right) { // 右depth; // 深度1getdepth(node-right, depth);depth--; // 回溯深度-1}return ;}int maxDepth(TreeNode* root) {result 0;if (root NULL) return result;getdepth(root, 1);return result;}
};简化代码
class solution {
public:int result;void getdepth(TreeNode* node, int depth) {result depth result ? depth : result; // 中if (node-left NULL node-right NULL) return ;if (node-left) { // 左getdepth(node-left, depth 1);}if (node-right) { // 右getdepth(node-right, depth 1);}return ;}int maxDepth(TreeNode* root) {result 0;if (root 0) return result;getdepth(root, 1);return result;}
};迭代法
使用迭代法的话使用层序遍历是最为合适的因为最大的深度就是二叉树的层数和层序遍历的方式极其吻合。
在二叉树中一层一层的来遍历二叉树记录一下遍历的层数就是二叉树的深度如图所示 所以这道题的迭代法就是一道模板题可以使用二叉树层序遍历的模板来解决的。
class Solution{
public:int maxDepth(TreeNode* root) {if(root NULL) return 0;queueTreeNode* que;que.push(root);int depth 0;while(!que.empty()){int size que.size();depth;for(int i 0;i size; i){TreeNode* node que.front();que.pop();if(node-left) que.push(node-left);if(node-right) que.push(node-right);}}return depth;}
}总结
1.使用前序中左右这样是从上往下就是深度的概念。
2.也可以使用后序遍历左右中这样就是从下往上就是高度的概念。使用前序求的就是深度使用后序求的是高度。
递归法始终不是很会层序遍历容易理解点。
10.二叉树最小深度
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明**叶子节点是指没有子节点的节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出2二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数后者节点数取决于高度从0开始还是从1开始
后序遍历其实求的是根节点到叶子节点的最小距离就是求高度的过程不过这个最小距离 也同样是最小深度。
在处理节点的过程中最大深度很容易理解最小深度就不那么好理解如图 题目中说的是最小深度是从根节点到最近叶子节点的最短路径上的节点数量。注意是叶子节点。
什么是叶子节点左右孩子都为空的节点才是叶子节点
递归法
后序遍历方式
确定递归函数的参数和返回值
参数为要传入的二叉树根节点返回的是int类型的深度。
int getDepth(TreeNode* node)确定终止条件
终止条件也是遇到空节点返回0表示当前节点的高度为0。
if (node NULL) return 0; 3.确定单层递归的逻辑
int leftDepth getDepth(node-left);
int rightDepth getDepth(node-right);
int result 1 min(leftDepth, rightDepth);//如果这么求的话没有左孩子的分支会算为最短深度。
return result;如果左子树为空右子树不为空说明最小深度是 1 右子树的深度。
反之右子树为空左子树不为空最小深度是 1 左子树的深度。
最后如果左右子树都不为空返回左右子树深度最小值 1 。
int leftDepth getDepth(node-left);//左
int rightDepth getDepth(node-right);//右
//中不做左右节点为空的判断的话出现空节点时就会返回最小值为 1 0 1的情况
if(node-left NULL node-right ! NULL){ // 当一个左子树为空右不为空这时并不是最低点return 1 rightDepth;
}
if(node-left !NULL node-right - NULL){// 当一个右子树为空左不为空这时并不是最低点return 1 leftDepth;
}
return 1 min(leftDepth,rightDepth);//左右孩子都为空遍历的顺序为后序左右中可以看出求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。
前序遍历方式
class Solution {
public:int result INT_MAX;//默认最大值void getDepth(TreeNode* node,int depth){if(node NULL) return ;//中if(node-left NULL node-right NULL){//满足叶子节点result min(result, depth);//更新结果return;}//左if(node-left ! NULL){//左子树getDepth(node-left,depth 1);}//右if(node-right ! NULL){//右子树getDepth(node-right,depth 1);}return ;}int minDepth(TreeNode* root) {if(root NULL) return 0;getDepth(root,1);return result;}
};迭代法
有当左右孩子都为空的时候才说明遍历到最低点了。如果其中一个孩子不为空则不是最低点
/*** 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) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {if(root NULL) return 0;queueTreeNode* que;que.push(root);int minDepth 0;while(!que.empty()){int size que.size();minDepth;for(int i 0; i size ; i ){TreeNode* node que.front();que.pop();if(node-left nullptr node-right nullptr){return minDepth;}if(node-left) que.push(node-left);if(node-right) que.push(node-right);}}return minDepth;}
};总结
1.什么是最小深度什么是叶子节点
根节点到叶子节点的最短距离。左右子节点都为空的节点就是叶子节点。
2.后序遍历左右中就是从下往上求的是高度每次把结果返回给父节点 最大高度 最大深度。
前序遍历中左右就是从上往下求的是深度。
11.完全二叉树节点个数
给你一棵 完全二叉树 的根节点 root 求出该树的节点个数。
完全二叉树 的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。
示例 1 输入root [1,2,3,4,5,6]
输出6迭代法
层序遍历记录遍历的节点数量就可以了
class Solution {
public:int countNodes(TreeNode* root) {if(root NULL) return 0;queueTreeNode* que;que.push(root);int num 1;while(!que.empty()){int size que.size();for(int i 0;i size; i){TreeNode* node que.front();que.pop();if(node-left){que.push(node-left);num; } if(node-right){que.push(node-right); num; } }}return num;}
};递归法
和求二叉树的深度写法类似。
确定递归函数的参数和返回值参数就是传入树的根节点返回就返回以该节点为根节点二叉树的节点数量所以返回值为int类型。
代码如下
int getNodesNum(TreeNode* cur) {}2.确定终止条件如果为空节点就返回0表示节点数为0.
if(cur NULL) return 0;3.确定单层递归逻辑先求左子树的节点数量再求右子树的节点数量最后取总和1加1是因为算上当前中间节点就是总的节点个数。
int left getNodesNum(cur-left);//左
int right getNodesNum(cur-right);//右
return leftright1;//中class Solution {
public:int getNodesNum(TreeNode* cur){if(cur nullptr) return 0;int left getNodesNum(cur-left);//左int right getNodesNum(cur-right);//右return 1 left right;//中//return 1 countNodes(root-left) countNodes(root-right);//简化代码}int countNodes(TreeNode* root) {if(root nullptr) return 0 ;return getNodesNum(root);}
};完全二叉树
利用了完全二叉树的特性不用遍历没有必要的节点。
在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2^(h-1) 个节点。【只允许最后一层有空缺结点且空缺在右边】 完全二叉树只有两种情况情况一就是满二叉树情况二最后一层叶子节点没有满。
情况1一个层数为k 的满二叉树总结点数为(2^k)-1。因此满二叉树的结点树一定是奇数个。*直接用 2^树深度 - 1 来计算注意这里根节点深度为1。
对于情况二分别递归左孩子和右孩子递归到某一深度一定会有左孩子或者右孩子为满二叉树然后依然可以按照情况1来计算。 可以看出如果整个树不是满二叉树就递归其左右孩子直到遇到满二叉树为止用公式计算这个子树满二叉树的节点数量。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢
在完全二叉树中如果递归向左遍历的深度等于递归向右遍历的深度那说明就是满二叉树。如图
在完全二叉树中如果递归向左遍历的深度不等于递归向右遍历的深度则说明不是满二叉树如图 那有录友说了这种情况递归向左遍历的深度等于递归向右遍历的深度但也不是满二叉树如图 如果这么想大家就是对 完全二叉树理解有误区了以上这棵二叉树它根本就不是一个完全二叉树
判断其子树是不是满二叉树如果是则利用公式计算这个子树满二叉树的节点数量如果不是则继续递归那么 在递归三部曲中第二部终止条件的写法应该是这样的
if (root nullptr) return 0;
// 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
TreeNode* left root-left;
TreeNode* right root-right;
int leftDepth 0, rightDepth 0; // 这里初始为0是有目的的为了下面求指数方便
while (left) { // 求左子树深度left left-left;leftDepth;
}
while (right) { // 求右子树深度right right-right;rightDepth;
}
if(leftDepth rightDepth){return (2 leftDepth) - 1;// 注意(21) 相当于2^2返回满足满二叉树的子树节点数量
}总体代码
class Solution {
public:int getNodesNum(TreeNode* cur){if(cur nullptr) return 0;//终止条件TreeNode* left cur-left;TreeNode* right cur-right;int leftDepth 0;int rightDepth 0;while(left){left left-left;leftDepth;}while(right){right right-right;rightDepth;}if(rightDepth leftDepth){return (2 leftDepth) - 1;//满足满二叉树节点的节点数}/*int leftTreeNum getNodesNum(root-left); // 左int rightTreeNum getNodesNum(root-right); // 右int result leftTreeNum rightTreeNum 1; // 中return result;*/return getNodesNum(cur-left) getNodesNum(cur-right) 1;//不满足的就继续递归}int countNodes(TreeNode* root) {if(root nullptr) return 0 ;return getNodesNum(root);}
};总结
1.又熟悉了完全二叉树、满二叉树的定义。
什么是完全二叉树只允许最后一层有空缺结点且空缺在右边的二叉树。完全二叉树只有两种情况情况一就是满二叉树情况二最后一层叶子节点没有满。
什么是满二叉树除最后一层无任何子节点外每一层上的所有结点都有两个子结点二叉树。
国内教程定义一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是(2^k) -1 则它就是满二叉树。
2.相比普通的二叉树方法**利用完全二叉树的特性不用遍历那些没有必要的节点。**判断左右节点是否满足满二叉树的条件满足的话用公式返回子树下面的总节点数量不满足就继续递归。
