宫水三叶的刷题日记

V1

2022/08/27阅读:29主题:前端之巅同款

662. 二叉树最大宽度 : 简单 DFS 运用题

题目描述

这是 LeetCode 上的 662. 二叉树最大宽度 ,难度为 中等

Tag : 「二叉树」、「DFS」、「哈希表」

给你一棵二叉树的根节点 root,返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的 null 节点,这些 null 节点也计入长度。

题目数据保证答案将会在  32 位 带符号整数范围内。

示例 1:

输入:root = [1,3,2,5,3,null,9]

输出:4

解释:最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。

示例 2:

输入:root = [1,3,2,5,null,null,9,6,null,7]

输出:7

解释:最大宽度出现在树的第 4 层,宽度为 7 (6,null,null,null,null,null,7) 。

示例 3:

输入:root = [1,3,2,5]

输出:2

解释:最大宽度出现在树的第 2 层,宽度为 2 (3,2) 。

提示:

  • 树中节点的数目范围是

DFS

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

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

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

Java 代码:

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root, 10);
        return ans;
    }
    void dfs(TreeNode root, int u, int depth) {
        if (root == nullreturn ;
        if (!map.containsKey(depth)) map.put(depth, u);
        ans = Math.max(ans, u - map.get(depth) + 1);
        dfs(root.left, u << 1, depth + 1);
        dfs(root.right, u << 1 | 1, depth + 1);
    }
}

TypeScript 代码:

let map = new Map<number, bigint>()
let ans = 0n
function widthOfBinaryTree(root: TreeNode | null): number {
    map.clear()
    ans = 0n
    dfs(root, 1n0)
    return Number(ans)
};
function dfs(root: TreeNode | null, u: bigint, depth: number): void {
    if (root == nullreturn 
    if (!map.has(depth)) map.set(depth, u)
    if (u - map.get(depth) + 1n > ans) ans = u - map.get(depth) + 1n
    dfs(root.left, u << 1n, depth + 1)
    dfs(root.right, u << 1n | 1n, depth + 1)
}
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.662 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1