草庐IT

【重要】LeetCode 662. 二叉树最大宽度

Frodo's blog 2023-03-28 原文

题目链接

注意事项

根据满二叉树的节点编号规则：若根节点编号为 u，则其左子节点编号为 u << 1，其右节点编号为 u << 1 | 1。

一个朴素的想法是：我们在 DFS过程中使用两个哈希表分别记录每层深度中的最小节点编号和最大节点编号，两者距离即是当前层的宽度，最终所有层数中的最大宽度即是答案。

而实现上，我们可以利用先 DFS 左节点，再 DFS 右节点的性质可知，每层的最左节点必然是最先被遍历到，因此我们只需要记录当前层最先被遍历到点编号（即当前层最小节点编号），并在 DFS 过程中计算宽度，更新答案即可。

关于编号溢出问题，之所以溢出仍能 AC 是因为测试数组中没有同层内「宽度」左端点不溢出，右端点溢出，同时该层就是最大宽度的数据点。
我们可以通过 u = u - map.get(depth) + 1 操作来对同层内的节点进行重新编号（使得同层最靠左的非空节点编号为1）。
通过重编号操作 我们可以消除由于深度加深带来的编号溢出问题。

代码

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root, 1, 0);
        return ans;
    }
    void dfs(TreeNode root, int u, int depth) {
        if (root == null) return ;
        if (!map.containsKey(depth)) map.put(depth, u);
        ans = Math.max(ans, u - map.get(depth) + 1);
        u = u - map.get(depth) + 1;
        dfs(root.left, u << 1, depth + 1);
        dfs(root.right, u << 1 | 1, depth + 1);
    }
}
LeetCode662depthrootlt算法与数据结构

有关【重要】LeetCode 662. 二叉树最大宽度的更多相关文章

  1. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  2. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  3. ruby - 在 Ruby 中实现二叉树 - 2

    我一直在尝试在Ruby中实现BinaryTree类，但我得到了stackleveltoodeep错误，尽管我似乎没有在该特定代码段中使用任何递归:1.classBinaryTree2.includeEnumerable3.4.attr_accessor:value5.6.definitialize(value=nil)7.@value=value8.@left=BinaryTree.new#stackleveltoodeephere9.@right=BinaryTree.new#andhere10.end11.12.defempty?13.(self.value==nil)?true:

  4. ruby - 获取数组中值的最大连续出现次数 - 2

    下面有没有更优雅的方法来实现这个:输入:array=[1,1,1,0,0,1,1,1,1,0]输出:4我的算法:streak=0max_streak=0arr.eachdo|n|ifn==1streak+=1elsemax_streak=streakifstreak>max_streakstreak=0endendputsmax_streak 最佳答案 类似于w0lf'sanswer,但通过从chunk返回nil来跳过元素:array.chunk{|x|x==1||nil}.map{|_,x|x.size}.max

  5. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  6. ruby - Camping 和 Sinatra 之间有什么重要区别吗？ - 2

    我的感觉是Camping和Sinatra之间的差异不是很大，您可以安全地选择其中任何一个并且没问题。但我想问问Ruby专家，这是不是真的。Sinatra和Camping微框架之间实际上有什么重要区别吗？您将如何决定使用哪一个？ 最佳答案 我知道的唯一显着区别是Camping像Rails一样基于MVC模式，并且与ActiveRecord耦合。Sinatra更加不可知。Camping也不再维护，而Sinatra正在积极开发中。仅这一点就足以让我们先看看Sinatra。编辑:感谢Philippe的更正，很高兴听到Camping的开发正在进

  7. Ruby:检查东亚宽度 (Unicode) - 2

    使用Ruby，我必须将字符串以柱状格式输出到终端。像这样:|row1|astringhere|etc|row2|anotherstring|etc我可以使用String#ljust和%s处理拉丁UTF8字符。但是当字符是韩文、中文等时就会出现问题。当英文行与包含韩文等的行交错时，列根本不会对齐。如何在此处实现列对齐？有没有办法以等同于固定宽度字体的方式输出亚洲字符？对于要在Vim中显示和编辑的文档怎么样？ 最佳答案 您的问题发生在CJK(中文/日文/韩文)full-widthandwidecharacters(也向下滚动图表)；这些

  8. ruby - =~ 运算符的顺序重要吗？ - 2

    下面两个语句除了编码风格有区别吗？/regex/=~"some_string_with_regex""some_string_with_regex"=~/regex/ 最佳答案 是的，有区别。正如在http://www.ruby-doc.org/core/classes/Regexp.html#M001232中提到的If=~isusedwitharegexpliteralwithnamedcaptures,capturedstrings(ornil)isassignedtolocalvariablesnamedbythecaptur

  9. ruby - capybara 增加最大允许页面加载时间 - 2

    我有一个页面，有时加载时间超过一分钟。假设这是预期的行为并且不会改变。在这些情况下，我得到Net::ReadTimeout。请注意，这是在通过单击上一页上的按钮导航到页面之后，而不是ajax请求。因此Capybara.using_wait_time没有帮助。我尝试了一些激进的方法(其中一些我知道行不通)，例如:设置page.driver.browser.manage.timeouts的implicit_wait、script_timeout和page_load。遍历整个对象空间并设置所有Selenium::WebDriver::Remote::Http::Default的timeout

  10. Ruby - 找到哈希最大值的键 - 2

    我有一个散列，我想返回散列最大值的键(或键/值对)。所以，如果只有一个真正的最大值，它将返回那个键；但是，如果有多个具有相同值的键/值对，它将返回所有这些键。我如何在Ruby中完成此操作？my_hash.max_by{|k,v|v}#onlyreturnsonekey/valuepair 最佳答案 如果你想要所有对，我会做类似的事情max=my_hash.values.maxHash[my_hash.select{|k,v|v==max}] 关于Ruby-找到哈希最大值的键，我们在Sta

随机推荐