662. 二叉树最大宽度

2024-01-08 12:00:05

题目

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

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

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

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

示例 1:

输入: root = [1,3,2,5,3,null,9]
输出: 4
解释: 最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。

代码与解析

不得不说三叶姐姐真牛掰,我有想过用高度和编号,但就卡在了编号怎么弄。三叶姐姐解答: 左侧编号是u << 1, 右侧编号是 u<<1 | 1,就是扩大2倍,|1是将最高位置为1,例如第二层,左边就是01,右边就是11这样子

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int ans = 0;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root, 1, 0);
        return ans;
    }
    public void dfs(TreeNode node, int u, int height) {
        if(node == null)    return;
        if(!map.containsKey(height)) map.put(height, u);
        u = u - map.get(height) + 1; //防止编号溢出
        ans = Math.max(ans, u);
        dfs(node.left, u << 1, height + 1);
        dfs(node.right, u << 1 | 1, height + 1);
    }
}

文章来源:https://blog.csdn.net/m0_51547272/article/details/135445163
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。