📃 题目描述

题目链接：662. 二叉树最大宽度 (opens new window)

🔔 解题思路

为了求宽度，不妨给二叉树编号（我这里是从 1 开始编号，从0开始也是一样的）：

按层遍历，不过就是最后个节点的编号减去第一个节点的编号加 1即可。

假设当前节点编号为 root.val，那么：

• 左子节点编号: root.val * 2
• 右子节点编号: root.val * 2 + 1

比如

	 2
  3	     9
7   2  null  4

编号后为

	 1
  2	     3
4   5  null  7

最大宽度为 7 - 4 + 1 = 4

具体代码如下：

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        root.val = 1;
        queue.offer(root);

        // 记录最大宽度
        int res = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 当前层的最小序号、最大序号
            int l = 0, r = 0;
            for (int i = 0; i < size; i ++) {
                TreeNode cur = queue.poll();
                if (i == 0) {
                    l = cur.val;
                }
                if (i == size - 1) {
                    r = cur.val;
                    res = Math.max(res, r - l + 1);
                }

                if (cur.left != null) {
                    cur.left.val = cur.val * 2;
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    cur.right.val = cur.val * 2 + 1;
                    queue.offer(cur.right);
                }
            }
            
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：