题解 | JAVA #二叉树的最大宽度# [P3]

可以这样去给每一层的node编号：

root = 0； 
root.left = root << 1;
root.right = (root << 1) + 1;


      A                        0    
    /   \                    /   \
   B     C       =>         00     01
  / \     \                /  \     \
 D   E     F             000  001   011

遍历就用preOrder recursive。parent根据自己的编号给child assign编号
遍历过程中用一个List<int[2]>去记录目前为止每层(0 based)看到过的的最大,最小编号。
遍历结束后把list里每一层的最大最小编号求差，输出最大差+1就是结果

比如:
第1层(B, C), list.get(1)结果应该是[00, 01], 说明这层的width是 1-0+1 = 2。
第2层(D, E, F), list.get(2)结果应该是[000, 011], 说明这层的width是 3-0+1 = 4。

import java.util.*;

public class Solution {
    public int widthOfBinaryTree (TreeNode root) {
      // e.g. list.get(x) -> {minIndex, maxIndex} at level x
      List<int[]> levelMinMax = new ArrayList<>();
      dfs(root, 0, 0, levelMinMax);
      
      int maxWidth = 0;
      for (int[] minMax : levelMinMax) {
        maxWidth = Math.max(minMax[1] - minMax[0] + 1, maxWidth);
      }
      return maxWidth;
    }
  
    void dfs(TreeNode root, int idx, int level, List<int[]> levelMinMax) {
      if (root == null) return;

      if (level > levelMinMax.size() - 1) {
        // 第一次走到这个level, 需要new int[].
        levelMinMax.add(new int[]{idx, idx});
      } else {
        // update min/max
        int[] minMax = levelMinMax.get(level);
        minMax[0] = Math.min(minMax[0], idx); 
        minMax[1] = Math.max(minMax[1], idx);
      }
      
      dfs(root.left, (idx << 1), level + 1, levelMinMax);
      dfs(root.right,(idx << 1) + 1, level + 1, levelMinMax);
    }
}

第二种方法 一样是存编号，但是用level-order traversal. 建一个class存node和编号

class nodeAndSeqNum {
  TreeNode node;
  int seq;
  nodeAndSeqNum(TreeNode node, int seq);
}

enqueue的时候计算编号
每层for-loop的第一个和最后一个求seq差, update global max.