LeetCode 662. 二叉树最大宽度(递归)
发布日期:2021-07-01 03:25:57
浏览次数:3
分类:技术文章
本文共 1497 字,大约阅读时间需要 4 分钟。
1. 题目
给定一个二叉树,编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树(full binary tree)结构相同,但一些节点为空。
每一层的宽度被定义为两个端点(该层最左和最右的非空节点,两端点间的null节点也计入长度)之间的长度。
示例 1:输入: 1 / \ 3 2 / \ \ 5 3 9 输出: 4解释: 最大值出现在树的第 3 层,宽度为 4 (5,3,null,9)。示例 2:输入: 1 / 3 / \ 5 3 输出: 2解释: 最大值出现在树的第 3 层,宽度为 2 (5,3)。示例 3:输入: 1 / \ 3 2 / 5 输出: 2解释: 最大值出现在树的第 2 层,宽度为 2 (3,2)。示例 4:输入: 1 / \ 3 2 / \ 5 9 / \ 6 7输出: 8解释: 最大值出现在树的第 4 层,宽度为 8 (6,null,null,null,null,null,null,7)。注意: 答案在32位有符号整数的表示范围内。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-width-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 记录深度,和每一层的最左侧节点位置(中序遍历每层第一次碰到的)
- 节点位置用树的数组实现方式(注意溢出,每层pos*2很快就溢出了,用ulong能过)
class Solution { int ans;public: int widthOfBinaryTree(TreeNode* root) { if(!root) return 0; vectorLeftPosOflv; ans = 1; dfs(root, 0, 0, LeftPosOflv); return ans; } void dfs(TreeNode* root, int depth, unsigned long pos, vector &LeftPosOflv) { if(!root) return; if(LeftPosOflv.size() <= depth)//第一次遇到的是该层最左边的 LeftPosOflv.push_back(pos); ans = max(ans, int(pos-LeftPosOflv[depth]+1)); dfs(root->left, depth+1, 2*pos+1, LeftPosOflv); dfs(root->right, depth+1, 2*pos+2, LeftPosOflv); }};
12 ms 16.3 MB
转载地址:https://michael.blog.csdn.net/article/details/106249487 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
做的很好,不错不错
[***.243.131.199]2024年04月30日 05时16分14秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
剑指offer:连续子数组的最大和(java)
2019-05-03
剑指offer:从1到n整数中1出现的次数(java)
2019-05-03
剑指offer:把数组排成最小的数(java)
2019-05-03
剑指offer:丑数(java)
2019-05-03
剑指offer:第一个只出现一次的字
2019-05-03
剑指offer:数组中的逆序对(java)
2019-05-03
剑指offer:两个链表的第一个公共结点(java)
2019-05-03
剑指offer:数字在排序数组中出现的次数(java)
2019-05-03
实时开发框架Meteor API解读系列<二>Core
2019-05-03
实时开发框架Meteor 实际应用系列<一>---文件的上传和下载
2019-05-03
实时开发框架Meteor API解读系列<四>Server connections
2019-05-03
实时开发框架Meteor API解读系列<六> DDP
2019-05-03
实时开发框架Meteor 实际应用系列<一>---文件的上传和下载[补充]
2019-05-03
实时开发框架Meteor API解读系列<七> Collection --01
2019-05-03
启用fcitx-qimpanel面板程序
2019-05-03
浅谈Q的基本实现
2019-05-03
iOS开发——cache自动清理方案探索
2019-05-03
阿里云短信服务(JAVA)
2019-05-03