关于后端: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)。

提醒：

树中节点的数目范畴是 $[1, 3000]$
$-100 <= Node.val <= 100$

依据满二叉树的节点编号规定：若根节点编号为 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, 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);
        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, 1n, 0)
    return Number(ans)
};
function dfs(root: TreeNode | null, u: bigint, depth: number): void {if (root == null) return 
    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)
}

工夫复杂度：$O(n)$
空间复杂度：$O(n)$

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

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于后端:662-二叉树最大宽度-简单-DFS-运用题

题目形容

DFS

最初