Java实现求二叉树的深度和宽度
作者：junjie 发布时间：2022-01-11 18:38:41
这个是常见的对二叉树的操作。总结一下：
设节点的数据结构，如下：
class TreeNode {
char val;
TreeNode left = null;
TreeNode right = null;
TreeNode(char _val) {
this.val = _val;
}
}
1.二叉树深度
这个可以使用递归，分别求出左子树的深度、右子树的深度，两个深度的较大值+1即可。
// 获取最大深度
public static int getMaxDepth(TreeNode root) {
if (root == null)
return 0;
else {
int left = getMaxDepth(root.left);
int right = getMaxDepth(root.right);
return 1 + Math.max(left, right);
}
}
2.二叉树宽度
使用队列，层次遍历二叉树。在上一层遍历完成后，下一层的所有节点已经放到队列中，此时队列中的元素个数就是下一层的宽度。以此类推，依次遍历下一层即可求出二叉树的最大宽度。
// 获取最大宽度
public static int getMaxWidth(TreeNode root) {
if (root == null)
return 0;
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
int maxWitdth = 1; // 最大宽度
queue.add(root); // 入队
while (true) {
int len = queue.size(); // 当前层的节点个数
if (len == 0)
break;
while (len > 0) {// 如果当前层，还有节点
TreeNode t = queue.poll();
len--;
if (t.left != null)
queue.add(t.left); // 下一层节点入队
if (t.right != null)
queue.add(t.right);// 下一层节点入队
}
maxWitdth = Math.max(maxWitdth, queue.size());
}
return maxWitdth;
}
0
投稿猜你喜欢
增加了用于处理MyBatis的两个bean：SqlSessionFactoryBean、MapperFactoryBean1、注册SqlSe- 1，Java中操作方法：import java.io.*; public class FileInputStreamTest &
- 承接上文 传送门一.完善登录功能按照常理，只有登陆过后才能进入首页，若没有登陆则应当直接跳转到登陆页面，这样的场景不就完美契合过滤器的功效吗
- 本文实例讲述了Android开发使用Drawable绘制圆角与圆形图案功能。分享给大家供大家参考，具体如下：1. 创建类RoundCircl
- 本文实例分析了C#中使用资源的方法。分享给大家供大家参考。具体如下：这里总结一个在C#中如何使用资源的方法如下:方法一、使用本地文件1、将本
- 即刻点赞展示点赞的数字增加和减少并不是整个替换，而是差异化替换。再加上动画效果就看的很舒服。自己如何实现这种数字切换呢？下面用一张图来展示我
- 前言最近在学习Kotlin这门语言，在项目开发中，运用到了单例模式。因为其表达方式与Java是不同的。所以对不同单例模式的实现进行了分别探讨
- 本文实例为大家分享了Android联系人字母排序的具体代码，供大家参考，具体内容如下实现思路：首先说下布局，整个是一个相对布局，最下面是一个
- 参考链接亲测试以下版本成功激活附激活教程。idea下载链接(对应版本号下载)：https://www.jetbrains.com/idea/
- Spring5路径匹配器PathPatternPathPattern 对url地址匹配的处理更加快速，它和AntPathMatcher 主要
- RestTemplate简介Spring RestTemplate 是 Spring 提供的用于访问 Rest 服务的客户端，RestTem
- 这篇文章主要介绍了springmvc处理模型数据Map过程解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,
- 值类型和引用类型作为两个非常基础而且很重要的概念，一般我们都是在最开始的时候学的，你听到的可能是这样的：值类型传递的是具体的值（副本），引用
- 一、整合原理二、导包(41个)1.hibernate（1）hibernate/lib/required（2）hibernate/lib/jp
- springboot通过URL方式访问外部资源遇到这个问题时翻阅百度，无外乎就是两种方式第一种在springboot 2.1.8中该方法已过
- spring security用了也有一段时间了，弄过异步和多数据源登录，也看过一点源码，最近弄rest，然后顺便搭oauth2，前端用js
- LRU简介LRU是Least Recently Used 近期最少使用算法，它就可以将长时间没有被利用的数据进行删除。实现最近面了阿里的外包
- 这篇文章主要介绍了设计模式在Spring框架中的应用汇总,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的
- Spring框架是一个优秀的多层J2EE系统框架，Spring本身没有提供对系统的安全性支持。Acegi是基于Spring IOC 和 AO
- 最近项目需要，需要做一个BMI指数的指示条，先上效果图： BMI指数从18到35，然后上面指示条的颜色会随着偏移量的变化而改变，数字显示当前
