算法训练营day16(二叉树03:最大深度,最小深度,完全二叉树节点数量)
第六章 二叉树part03
今日内容：
● 104.二叉树的最大深度 559.n叉树的最大深度
● 111.二叉树的最小深度
● 222.完全二叉树的节点个数
迭代法，大家可以直接过，二刷有精力的时候 再去掌握迭代法。
详细布置
104.二叉树的最大深度 （优先掌握递归）
什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。
大家 要先看视频讲解，就知道以上我说的内容了，很多录友刷过这道题，但理解的还不够。
题目链接/文章讲解/视频讲解： https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html
111.二叉树的最小深度 （优先掌握递归）
先看视频讲解，和最大深度 看似差不多，其实 差距还挺大，有坑。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html
222.完全二叉树的节点个数（优先掌握递归）
需要了解，普通二叉树 怎么求，完全二叉树又怎么求
题目链接/文章讲解/视频讲解：https://programmercarl.com/0222.%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%8A%82%E7%82%B9%E4%B8%AA%E6%95%B0.html
往日任务
● day 1 任务以及具体安排：https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排：https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排：https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排：https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排：https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排：https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排：https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排：https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排：https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排：https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排：https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排：https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNvday16
二叉树的最大深度
递归法
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return 1 + Math.max( maxDepth(root.left), maxDepth(root.right));
//后序遍历
}
}
二叉树的最小深度
递归法
class Solution {
public int minDepth(TreeNode root) {
//后序遍历
if( root == null ) return 0;
if( root.left == null && root.right != null)
return minDepth( root.right) + 1;
if( root.left != null && root.right == null)
return minDepth( root.left) + 1;
return Math.min( minDepth(root.left), minDepth( root.right) ) + 1;
}
}
完全二叉树的节点数量
递归法
//普通二叉树节点的数量,后序遍历
class Solution {
public int countNodes(TreeNode root) {
if( root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
//完全二叉树的节点数量,后序遍历
//用到完全二叉树的特性,如果两侧的深度相同,那么中间节点一定是满的,这样就不用遍历所有的节点了
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0;
while (left != null) { // 求左子树深度
left = left.left;
leftDepth++;
}
while (right != null) { // 求右子树深度
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // (2<<1) 相当于2^2，leftDepth初始为0没问题
}
return countNodes(root.left) + countNodes(root.right) + 1;
//return countNodes(left) + countNodes(right) + 1;
//left 后面在while里发生了变化,不能直接用
}
}
小节:前序求深度,后序求高度(关键在于是把子节点处理完了返回给父节点,还是处理父节点传递给子节点)
感谢大佬分享:
代码随想录-算法训练营day16【二叉树03：二叉树的最大深度、二叉树的最小深度、完全二叉树的节点个数】-CSDN博客