求得任意树的宽度 LeetCode662. Maximum Width of Binary Tree

这个问题适用求出不知宽度的树的度（或者说宽度）。

思路在哪里呢？

记录每一层的最左端节点的下标L，用同一层的节点坐标减 L 能求出宽度，然后取每层宽度的最大值就可以了。

Java：（其实什么语言思路都一样）

    int max = 0;
    public int widthOfBinaryTree(TreeNode root) {
        helper(root, new ArrayList<Integer>(), 0, 0);
        return max;
    }
    
    void helper(TreeNode root, List<Integer> lefts, int level, int index){
        if(root == null) return;
        //因为每一层都只有一个最左的节点，所以可以用这个条件保证lefts加入的节点坐标一定是这层最左节点的坐标
        if(level == lefts.size()){
           lefts.add(index); 
        }
        //更新max，其实只用最右端的节点减就够了，懒得实现了
        max = Math.max(max, index - lefts.get(level) + 1);
        //递归下一层
        helper(root.left, lefts, level + 1, index * 2);
        helper(root.right, lefts, level + 1, index * 2 + 1);
    }