662. Maximum Width of Binary Tree

• https://leetcode.com/problems/maximum-width-of-binary-tree/description/

• 给一棵树，算这个树里面存在的最大宽度。

思路

• 因为宽度是每一层来计算，考虑层次遍历
• 因为要考虑空元素所占用的位置，所以需要记录每个节点的 index
• 每个节点的 index 可以根据上一层的计算
• 例如
• 第一层，root 节点包含左右两个节点，则 root 节点 index=0，
• 第二层，左节点 index=0，右节点 index=1，第三层
• 第三层，最左边节点 index=0，左边第二个 index=1，右边第一个 index=2（上一层 index*2），右边第二个 index=3（上一层 index*2 + 1））
• 以此类推
• 本层最大宽度为最左侧节点的 index 到本层所有节点的距离最大值
• 利用层次遍历计算所有 index 并计算最大距离即可（这里存储 index 可以使用 Pair）
• https://leetcode.com/problems/maximum-width-of-binary-tree/solutions/3436593/image-explanation-why-long-to-int-c-java-python/?languageTags=java

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        int maxWidth = 0;

        Queue<Pair<TreeNode, Integer>> nodes = new LinkedList<>();

        if(root != null){
            nodes.add(new Pair(root, 0));
        }

        while(!nodes.isEmpty()){
            int n = nodes.size();
            int starting = nodes.peek().getValue();

            for(int i = 0; i < n; i++){
                Pair<TreeNode, Integer> pair = nodes.poll();
                TreeNode tmp = pair.getKey();
                int index = pair.getValue();
                if(tmp.left != null){
                    nodes.add(new Pair(tmp.left, index * 2));
                }
                if(tmp.right != null){
                    nodes.add(new Pair(tmp.right, index * 2 + 1));
                }
              maxWidth = Math.max(maxWidth, index - starting + 1);
            }
        }

        return maxWidth;


    }
}