662. Maximum Width of Binary Tree - Medium

前往題目

想法

• BFS

思路

紀錄index就可以完美解決

1. 一般的BFS
2. 每個點除了把自身加入到queue，還要加入節點的index，表示在這層當中的index
3. 利用節點的index就可以在最後算出這層可以多長
4. 循環每層到最後取最大值

Code

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        int res = 0;
        // Node, index
        Queue<Pair<TreeNode, Integer>> q = new LinkedList();
        q.offer(new Pair(root, 0));

        while (!q.isEmpty()) {
            int len = q.size();
            // Starting index of the current level
            int initialIndex = q.peek().getValue();
            // Index of the current node
            int index = 0;

            for (int i = 0; i < len; ++i) {
                Pair<TreeNode, Integer> p = q.poll();
                TreeNode curNode = p.getKey();
                index = p.getValue();

                if (curNode.left != null) {
                    q.offer(new Pair(curNode.left, index * 2));
                }
                if (curNode.right != null) {
                    q.offer(new Pair(curNode.right, index * 2 + 1));
                }
            }
            // Cal. the length
            res = Math.max(res, index - initialIndex + 1);
        }
        return res;
    }
}