662. 二叉树最大宽度

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

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

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

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

示例 1：

img

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

示例 2：

img

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

示例 3：

img

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

提示：

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

解题思路：

  1. 新建类用于记录当前节点以及当前节点值索引的关系
  2. 然后层序遍历该树，因为对于完全二叉树来说，某一个节点的索引值为x，则它左孩子的索引值为2x，它右孩子的索引值为2x+1
  3. 所以只要计算出每一层的宽度，即每层节点的最大索引减去每层节点的最小索引+1即为该层的宽度，
  4. 比较得出最大值即可

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//用于标识当前节点和当前节点的索引的关系
//对于满二叉树来说，如果一个节点的索引值为x
//则他左孩子的索引值为2x,他右孩子索引值为2x * 1
class Pair {
    private TreeNode treeNode;
    private Integer index;

    public TreeNode getTreeNode() {
        return treeNode;
    }

    public Integer getIndex() {
        return index;
    }

    public Pair(TreeNode treeNode, Integer index) {
        this.treeNode = treeNode;
        this.index = index;
    }
}


public class Lc662 {

    public int widthOfBinaryTree(TreeNode root) {
        //广度优先遍历，使用队列辅助
        ArrayDeque<Pair> que = new ArrayDeque<>();
        //根节点及其索引
        Pair rootPair = new Pair(root, 1);
        que.add(rootPair);

        int res = 1;

        while (!que.isEmpty()) {
            //每层的节点个数
            int length = que.size();
            //每层的第一个节点索引和最后一个节点索引
            int firstIndex = 0;
            int lastIndex = 0;

            while (length > 0) {
                //获取当前节点信息
                Pair curPair = que.poll();
                TreeNode node = curPair.getTreeNode();
                Integer index = curPair.getIndex();
                //如果开始索引等于0，则证明该节点为当前层第一个节点，记录下来
                if (firstIndex == 0){
                    firstIndex = index;
                }

                //左节点入队
                if (node.left != null) {
                    que.offer(new Pair(node.left, index * 2));
                }
                //右节点入队
                if (node.right != null) {
                    que.offer(new Pair(node.right, index * 2 + 1));
                }

                //记录当前层最后一个节点的索引值
                lastIndex = index;
                length--;
            }

            //当前层的最后一个元素索引值减去当前层的第一个元素索引值+1,即为当前层的最大宽度
            res = Math.max(res, lastIndex - firstIndex + 1);

        }
        return res;


    }
}