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

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;
        }
        root.val = 1;
	  // 对树中所有节点进行编号,左节点2n，右节点2n+1
        pre(root);
	  
	  // 声明一个队列存储节点
        Deque<TreeNode> deque = new ArrayDeque<>();
	  // 声明一个map存储节点以及节点所在的层数，key：节点，value：层数
        Map<TreeNode, Integer> map = new HashMap<>();
	  // 根节点入队，入map
        deque.add(root);
        map.put(root, 1);

	  // 初始化层数、最大宽度
        int level = 1;
        int maxWidth = 0;

        while(!deque.isEmpty()){
		  // 节点出队
            TreeNode curNode = deque.poll();
		  // 获取出队节点所在层数
            Integer curLevel = map.get(curNode);
		  // 获取当前层数最左侧索引
            int index = (int) Math.pow(2, curLevel - 1);
		  // 如果节点所在层与当前层数一致
            if(curLevel == level){
			  // 计算最大宽度
                maxWidth = Math.max(maxWidth, curNode.val - index + 1);
            } else{
			  // 如果不一致，层数加一
                level++;
			  // 重新计算最大宽度
                maxWidth = Math.max(maxWidth, 1);
            }
		  // 左节点不为空，入队列，入map
            if(curNode.left != null){
                deque.add(curNode.left);
                map.put(curNode.left, curLevel+1);
            }
		  // 右节点不为空，入队列，入map
            if(curNode.right != null){
                deque.add(curNode.right);
                map.put(curNode.right, curLevel+1);
            }
        }
        return maxWidth;
    }

    public void pre(TreeNode root){
        if(root.left != null){
            root.left.val = root.val * 2;
            pre(root.left);
        }
        if(root.right != null){
            root.right.val = root.val * 2 + 1;
            pre(root.right);
        }
    }


}