代码随想录算法训练营day16 | leetcode ● 104.二叉树的最大深度 559.n叉树的最大深度 ● 111.二叉树的最小深度 ● 222.完全二叉树的节点个数
2024-10-20 06:44:04
基础知识
二叉树的多种遍历方式，每种遍历方式各有其特点
LeetCode 104.二叉树的最大深度
分析1.0
往下遍历深度++，往上回溯深度--
class Solution {
int deep = 0, max = 0;
public int maxDepth(TreeNode root) {
preOrder(root);
return max;
}
void preOrder(TreeNode p){
if(p == null){
return;
}
deep++;
max = Math.max(deep, max);
preOrder(p.left);
preOrder(p.right);
deep--;
}
}分析2.0
这个思路值得背诵
class solution {
/**
* 递归法
*/
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}LeetCode 111.二叉树的最小深度
分析1.0
同最大深度一样的考虑，每次求最小值，最小值只能在叶节点取得
class Solution {
int deep = 0, min = 100001;
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
preOrder(root);
return min;
}
void preOrder(TreeNode p){
if(p == null){
return;
}
deep++;
if(p.left == null && p.right == null){
min = Math.min(deep, min);
}
preOrder(p.left);
preOrder(p.right);
deep--;
}
}求最小值结果变量要初始化为数据集的最大值，求最大值要初始化为数据集的最小值
分析2.0
class Solution {
/**
* 递归法，相比求MaxDepth要复杂点
* 因为最小深度是从根节点到最近**叶子节点**的最短路径上的节点数量
*/
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if (root.left == null) {
return rightDepth + 1;
}
if (root.right == null) {
return leftDepth + 1;
}
// 左右结点都不为null
return Math.min(leftDepth, rightDepth) + 1;
}
}LeetCode 222.完全二叉树的节点个数
分析1.0
完全二叉树求节点个数，知道层数+最后一层节点数即可
目前只知道根节点，遍历一下O(n）得出结论，但是要好于O（n），考虑完全二叉树特点 ？
空节点都在最后一层的右边，从根节点一直访问右孩子，知道访问到叶子节点，这时可能访问到最后一层或倒数第二层
失误
分析2.0
class Solution {
/**
* 针对完全二叉树的解法
*
* 满二叉树的结点数为：2^depth - 1
*/
public int countNodes(TreeNode root) {
if (root == null) return 0;
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0; // 这里初始为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;
}
}分析3.0
普通二叉树
class Solution {
// 通用递归解法
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}总结
- 使用前序求的就是深度，使用后序求的是高度
- 求最小值结果变量要初始化为数据集的最大值，求最大值要初始化为数据集的最小值
- 二叉树有一个很好的结构特点，某个操作可以平等地施加于所有节点，这样递归就特别方便，要求什么先求它的孩子
- 判断一颗完全二叉树是不是满二叉树向左右两边遍历
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch
最新文章
- mysql 5.5 修改字符编码
- CacheManager COUNTER
- HTML 学习笔记 CSS样式（链接）
- [KOJ95603]全球奥运
- 【GoLang】golang HTTP GET/POST JSON的服务端、客户端示例，包含序列化、反序列化
- Repeater 使用方法
- C语言实现快速排序
- DDD：两篇不错的文章
- java 8-6 抽象的练习
- linux [Fedora] 下的 "飞秋/飞鸽传书"
- Django搭建及源码分析(二)
- VIM 及正则表达式
- [IDEs]Eclipse自动格式化代码
- JVM基础02-class文件
- UIApplicationDelegate 协议 浅析
- return和throw某些特性相似
- 向JSP中静态导入HTML文件时,运行jsp时,html中中文产生乱码问题最简单的解决方法
- mybatis四大接口之 ParameterHandler
- 斯坦福《机器学习》Lesson1-3感想-------3、线性回归二
- python-计算器实现