LeetCode : 662. Maximum Width of Binary Tree

[congr]

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

[congr]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        LinkedList<TreeNode> q = new LinkedList(); // use LinkedList for peekLast()
        q.add(root);

        int width = 0;
        while (!q.isEmpty()) {
            width = Math.max(width, q.peekLast().val - q.peek().val + 1); // !!!
            for (int size = q.size(); size > 0; size--) {
                TreeNode node = q.remove();

                if (node.left != null) {
                    node.left.val = node.val * 2;
                    q.add(node.left);    
                }
                if (node.right != null) {
                    node.right.val = node.val * 2 + 1;
                    q.add(node.right);    
                }
            }
        }

        return width;
    }
}