二叉树最大宽度-学会这个技巧-类似题目秒杀

在这里插入图片描述

代码逻辑

这道题就是给每个节点编号，根节点是1，然后左子节点就是父节点编号乘2，右子节点是父节点编号乘2再加1。

层序遍历的时候，每一层的宽度就等于这层最右边的编号减去最左边的编号再加1，把所有层遍历一遍取个最大值就行了。

代码里用 nq[] 存节点，iq[] 存对应的编号，l 和 r 两个指针来模拟队列操作。

完整代码

 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


public static int MAXN = 3001;
public static TreeNode[] nq = new TreeNode[MAXN];  // 节点队列
public static int[] iq = new int[MAXN];            // 编号队列
public static int l, r;                            // 队列的左右指针

public static int widthOfBinaryTree(TreeNode root) {
    int ans = 1;
    l = r = 0;
    
    // 初始化：根节点入队，编号为1
    nq[r] = root;
    iq[r++] = 1;
    
    while (l < r) {
        int size = r - l;  // 当前层的节点数量
        
        // 计算当前层的宽度
        ans = Math.max(ans, iq[r - 1] - iq[l] + 1);
        
        // 处理当前层的所有节点
        for (int i = 0; i < size; i++) {
            TreeNode node = nq[l];
            int id = iq[l++];
            
            // 左子节点入队
            if (node.left != null) {
                nq[r] = node.left;
                iq[r++] = id * 2;
            }
            
            // 右子节点入队
            if (node.right != null) {
                nq[r] = node.right;
                iq[r++] = id * 2 + 1;
            }
        }
    }
    
    return ans;
}