二叉树最大宽度 Maximum Width of Binary Tree
2024-09-29 22:23:43
2018-07-27 15:55:13
问题描述:
问题求解:
题目中说明了最后的宽度计算其实是按照满二叉树来进行计算的,也就是说如果我们能够得到每层最左边的节点编号和最右边的节点编号,那么本题就可以进行解决了。
另外,在如何编号的问题上,既然是满二叉树,那么编号的方式自然是父节点i,左子节点2 * i,右子节点2 * i + 1。
public int widthOfBinaryTree(TreeNode root) {
return helper(root, 0, 1, new ArrayList<Integer>(), new ArrayList<Integer>());
} private int helper(TreeNode root, int layer, int index, List<Integer> begin, List<Integer> end) {
if (root == null) return 0;
if (begin.size() == layer) {
begin.add(index);
end.add(index);
}
else end.set(layer, index);
int cur = end.get(layer) - begin.get(layer) + 1;
int l = helper(root.left, layer + 1, 2 * index, begin, end);
int r = helper(root.right, layer + 1, 2 * index + 1, begin, end);
return Math.max(cur, Math.max(l, r));
}
最新文章
- Robot Framework用户手册 (版本:3.0)
- quantile normalization原理
- Homebrew安装及使用
- ThinkPHP5 隐藏接口里面的index.php
- Jquery 基本知识(二)
- 20151217JS便签
- javaWeb request乱码处理
- 重命名myclipse中web项目名称的过程
- javamail模拟邮箱功能发送电子邮件-中级实战篇【新增附件发送方法】(javamail API电子邮件实例)
- Set up your first C# test with NUnit or resharper
- 你需要知道的九大排序算法【Python实现】源码
- Linq 查询基本操作
- Java中的图形界面编程
- Android显示GIF动画完整示例(二)
- POJ 1222 EXTENDED LIGHTS OUT (熄灯问题)
- python中多继承C3算法研究
- django内置分页功能扩展
- 【Qt5】Windows下配置程序的产品、公司、版权、版本号等详细信息
- .Net Core Package lose or not match
- MySQL Yum存储库 安装、升级、集群
热门文章
- 关于gg_bd_ad_720x90.js和follow.js
- RPC框架原理剖析(含实例)(转)
- python之路----面向对象中的内置函数
- OpenCV Using Python——基于SURF特征提取和金字塔LK光流法的单目视觉三维重建 (光流、场景流)
- bzoj5470 / P4578 [FJOI2018]所罗门王的宝藏
- Linux下useradd命令创建的用户不能登录的问题
- wireshark不支持抓localhost/127.0.0.1的包解决方法
- 01: vue.js安装
- golang debug调试
- ";/var/lib/mysql/mysql.sock";不存在解决办法