二叉树最大宽度

// Java Stream solution
// 思路：使用广度优先搜索 (BFS) 遍历树的每一层。使用列表保存每层的节点和位置，然后使用stream求最大宽度。
import java.util.*;
 
public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int maxWidth = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        while (!queue.isEmpty()) {
            int size = queue.size();
            int min = queue.peek().getValue();
            List<Integer> positions = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode node = pair.getKey();
                int curId = pair.getValue() - min;
                positions.add(curId);
                if (node.left != null) queue.offer(new Pair<>(node.left, curId * 2 + 1));
                if (node.right != null) queue.offer(new Pair<>(node.right, curId * 2 + 2));
            }
            maxWidth = Math.max(maxWidth, positions.stream().max(Integer::compare).orElse(0) - positions.stream().min(Integer::compare).orElse(0) + 1);
        }
        return maxWidth;
    }
}
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) { this.key = key; this.value = value; }
    public K getKey() { return key; }
    public V getValue() { return value; }
}