import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;public class test15 {public static class Node{public int value;public Node left;public Node right;public Node(int data){this.value = data;}}//按层次遍历二叉树并打印每个节点的值，使用了队列来实现广度优先搜索（BFS）public static void level(Node head){if(head == null){return;}Queue<Node> queue = new LinkedList<>();queue.add(head);while (!queue.isEmpty()){Node cur = queue.poll();System.out.println(cur.value);if(cur.left != null){queue.add(cur.left);}if(cur.right != null){queue.add(cur.right);}}}//求树的最大宽度//方法1使用HashMappublic static int maxWidthUseMap(Node head){if(head == null){return 0;}Queue<Node> queue= new LinkedList<>();queue.add(head);//key在哪一层为value的值HashMap<Node , Integer> levelMap= new HashMap<>();levelMap.put(head ,1);int curLevel = 1;//当前统计哪一层的宽度int curLevelNodes = 0;//当前层的宽度为多少int max = 0;while (!queue.isEmpty()){Node cur = queue.poll();int curNodeLevel = levelMap.get(cur);if(cur.left != null){levelMap.put(cur.left  ,curNodeLevel +1);queue.add(cur.left);}if(cur.right != null){levelMap.put(cur.left , curNodeLevel + 1);queue.add(cur.right);}if(curNodeLevel == curLevel){curLevelNodes++;}else{max = Math.max(max , curLevelNodes);curLevel++;curLevelNodes =1;}}max = Math.max(max , curLevelNodes);return  max;}//方法2不用HashMappublic static int  maxWidthNoMap(Node head){if(head == null){return 0;}Queue<Node> queue = new LinkedList<>();queue.add(head);Node curEnd = head;//当前层最后一个节点是谁Node nextEnd = null;//如果有下一层，那么下一层最后节点是谁int max =0;int curLevelNodes = 0;//当前层的节点数while (!queue.isEmpty()){Node cur = queue.poll();if(cur.left != null){queue.add(cur.left);nextEnd = cur.left;}if(cur.right != null){queue.add(cur.right);nextEnd = cur.right;}curLevelNodes++;if(cur == curEnd){max = Math.max(max , curLevelNodes);curLevelNodes = 0;curEnd = nextEnd;}}return max;}
}