Maximum Width of Binary Tree

Question

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Solution

第一次寫的時候試著用 level order traversal，但有 test case 過不了。看了解答後，訣竅在於：要記錄該 level leftmost 跟 rightmost 的 index，然後取最大值。至於該如何知道 leftmost, rightmost 呢？就可以利用樹的特性：若 root 的index 是 i，則 left child 是 2i，right child 是 2i + 1。於是可以寫出以下的答案

public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return helper(root, 0, 1, new ArrayList<Integer>(), new ArrayList<Integer>());
    }

    public int helper(TreeNode root ,int level, int order, List<Integer> start, List<Integer> end) {
        if (root == null) {
            return 0;
        }

        if (start.size() == level) {
            start.add(order);
            end.add(order);
        } else {
            end.set(level, order);
        }

        int cur = end.get(level) - start.get(level) + 1;
        int left = helper(root.left, level + 1, 2 * order, start ,end);
        int right = helper(root.right, level + 1, 2 * order + 1, start, end);
        return Math.max(cur, Math.max(left, right));
    }
}

其實即便是看了這個解答，也讓我想了一陣子為什麼要這樣解。卡住的地方有：

1. 為什麼 start.size() == level 時，要在 start 跟 end list 加入 order？ 這是因為判斷式所代表的情況為剛進入到新的一層，所以在 start 跟 end 加入最新一層的 leftmost index

2. 為什麼最後 return Math.max(cur, Math.max(left, right)) 這點其實想了一下，原因在於每當有點加入 end 時，我們就必須去更新一次當前 level leftmost 跟 rightmost 的距離是多少。因為我們不會知道當走到 right 時還有沒有 node 當我們的 rightmost

另外，也可以參考另一個用 global variable 代表 max 的解法

private int max = 1;
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        List<Integer> startOfLevel = new LinkedList<>();
        helper(root, 0, 1, startOfLevel);
        return max;
    }
    public void helper(TreeNode root, int level, int index, List<Integer> list) {
        if (root == null) return;
        if (level == list.size()) list.add(index);
        max = Math.max(max, index + 1 - list.get(level));
        helper(root.left, level + 1, index * 2, list);
        helper(root.right, level + 1, index * 2 + 1, list);
    }