题解 | #二叉树的最大宽度#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int widthOfBinaryTree (TreeNode root) {
        // write code here
        if(root == null) return 0;
        int maxWidth = 0;
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(root, 1));
        while(!q.isEmpty()) {
            int sz = q.size();
            int start = 0, end = 0;
            for(int i = 0; i < sz; i++) {
                Pair curPair = q.poll();
                TreeNode curNode = curPair.node;
                int curId = curPair.id;
                if(i == 0) {
                    start = curId;
                }
                if(i == sz-1) {
                    end = curId;
                }
                if(curNode.left != null) {
                    q.offer(new Pair(curNode.left, curId * 2));
                }
                if(curNode.right != null) {
                    q.offer(new Pair(curNode.right, curId * 2 + 1));
                }
            }
            maxWidth = Math.max(maxWidth, end - start + 1);
        }
        return maxWidth;
    }
}

class Pair {
    TreeNode node;
    int id;

    public Pair(TreeNode node, int id) {
        this.node = node;
        this.id = id;
    }
}