树的最大宽度：求二叉树最宽的层有多少个结点
关键在于建立一种发现层结束的机制。
方法一：通过新层的到来判断老层的结束
申请一个队列和一个HashMap，一个结点入队的时候在map里记录该节点在哪一层。那么，该结点弹出时就可以通过map得到该结点在哪一层。接下来，按层遍历二叉树的时候，每遍历到一个结点就把该结点所在的层数记录到map表里面。如果当前结点所在的层数跟当前正在统计宽度的那一层相等，说明老层还没有结束，所以当前层的宽度需要加1，如果不相等的话，说明老层已经结束，新层开始了。因为是通过新层的到来来判断老层的结束，最后一层是没有新层到来的。
方法二：通过老层的结束计算最大宽度。设置两个关键变量：当前层最右结点（curEnd），下一层最右的结点（nextEnd）。只需要用到一个队列，不需要用到哈希表
package com.harrison.class07; import java.util.HashMap; import java.util.LinkedList; import java.util.Queue; public class Code04_TreeMaxWidth { public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static int maxWidthUseMap(Node head) { if(head==null) { return 0; } Queue<Node> queue=new LinkedList<>(); queue.add(head); HashMap<Node, Integer> levelMap=new HashMap<>(); levelMap.put(head, 1); int curLevel=1;// 当前正在统计哪一层的宽度 int curLeverlNodes=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.right, curNodeLevel+1); queue.add(cur.right); } if(curNodeLevel==curLevel) { curLeverlNodes++; }else {// 新的层开始 max=Math.max(max, curLeverlNodes); curLevel++; curLeverlNodes=1; } } // 因为是通过新层的到来来判断老层的结束，最后一层是没有新层到来的 max=Math.max(max, curLeverlNodes); return max; } public 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 curLevelNodes=0; int max=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; } public static Node generateRandomBST(int maxLevel,int maxValue) { return generate(1, maxLevel, maxValue); } public static Node generate(int level,int maxLevel,int maxValue) { if(level>maxLevel || Math.random()<0.5) { return null; } Node head=new Node((int)(Math.random()*maxValue)); head.left=generate(level+1, maxLevel, maxValue); head.right=generate(level+1, maxLevel, maxValue); return head; } public static void main(String[] args) { int maxLevel=10; int maxValue=100; int testTimes=1000000; for(int i=0; i<testTimes; i++) { Node head=generateRandomBST(maxLevel, maxValue); if(maxWidthUseMap(head)!=maxWidthNoMap(head)) { System.out.println("oops"); } } System.out.println("finish"); } }
