【字节二面算法】NO662 二叉树最大宽度

[字节二面算法] 662. 二叉树最大宽度

给你一棵二叉树的根节点 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

暴力模拟空节点(超时

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        var ans = 0;
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            var count = queue.size();
            var widthCount = 0;
            var nullCount = 0;
            boolean flag = false;
            while(count-- > 0) {
                TreeNode poll = queue.poll();
                if(poll != null) {
                    System.out.print(poll.val + " ");
                    flag = true;
                    queue.add(poll.left);
                    queue.add(poll.right);

                    widthCount += nullCount + 1;
                    nullCount = 0;
                } else {
                    System.out.print("* ");
                    queue.add(null);
                    queue.add(null);
                    if(widthCount > 0) {
                        nullCount++;
                    }
                }
            }
            System.out.println();
            if(!flag) {
                break;
            }

            ans = Math.max(widthCount, ans);
        }
        return ans;
    }
}

利用层序遍历的性质

​ 记录节点的编号，然后用同一层的最大节点编号减去最小然后+1就是该层的最大宽度了。

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        var ans = 0;
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        Map<TreeNode, Long> map = new HashMap<>();
        map.put(root, 1L);
        while (!queue.isEmpty()) {
            var count = queue.size();
            var min = Long.MAX_VALUE;
            var max = Long.MIN_VALUE;
            while(count-- > 0) {
                TreeNode poll = queue.poll();
                var cur = map.get(poll);
                min = Math.min(min, cur);
                max = Math.max(max, cur);
                if(poll.left != null) {
                    queue.add(poll.left);
                    map.put(poll.left, cur * 2);
                }
                if(poll.right != null) {
                    queue.add(poll.right);
                    map.put(poll.right, cur * 2 + 1);
                }
            }
            ans = (int) Math.max(ans, max - min + 1);
        }
        return ans;
    }
}

原来可以这么写。。

​ 和上面的思路是一样的，这题并不难，其实最开始也想到用编号的方法，但是想着给的树节点定义是改变不了的，所以模拟超时之后又想到了使用map，然后看到别人其实是直接定义一个新类嵌套了树节点，这样的话就省去了map集合的操作时间消耗，学到了学到了

/**
 * 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 {
    public class QueueNode {
        TreeNode root;
        long index;

        QueueNode(TreeNode root, long index) {
            this.root = root;
            this.index = index;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        var ans = 1;
        Queue<QueueNode> queue = new LinkedList<>();
        queue.add(new QueueNode(root, ans));
        while(!queue.isEmpty()) {
            var size = queue.size();
            var first = 0L;
            var last = 0L;
            for(var i = 0; i < size; i++) {
                QueueNode poll = queue.poll();
                var index = poll.index;
                if(i == 0) {
                    first = index;
                    // 注意这里
                    last = index;
                } else if (i == size - 1 ){
                    last = index;
                }
                var left = poll.root.left;
                var right = poll.root.right;
                if(left != null) {
                    queue.add(new QueueNode(left, index * 2));
                }
                if(right != null) {
                    queue.add(new QueueNode(right, index * 2 + 1));
                }
            }
            ans = (int) Math.max(ans, last - first + 1);
        }
        return ans;
    }
}