package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * https://leetcode.com/problems/maximum-width-of-binary-tree/
 */
public class Problem662 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        int max = 0;
        int height = height(root);
        Queue<NodeLevel> queue = new LinkedList<>();
        queue.add(new NodeLevel(1, root));
        int level = 1;
        List<NodeLevel> tmp = new ArrayList<>();
        while (!queue.isEmpty()) {
            NodeLevel current = queue.remove();
            if (level < current.level) {
                level = current.level;
                max = Math.max(max, count(tmp));
                tmp = new ArrayList<>();
            }
            tmp.add(current);
            if (current.level < height) {
                if (current.node != null) {
                    if (current.node.left != null) {
                        NodeLevel n = new NodeLevel(current.level + 1, current.node.left);
                        queue.add(n);
                    } else {
                        NodeLevel n = new NodeLevel(current.level + 1, null);
                        queue.add(n);
                    }
                    if (current.node.right != null) {
                        NodeLevel n = new NodeLevel(current.level + 1, current.node.right);
                        queue.add(n);
                    } else {
                        NodeLevel n = new NodeLevel(current.level + 1, null);
                        queue.add(n);
                    }
                } else {
                    queue.add(new NodeLevel(current.level + 1, null)); // left
                    queue.add(new NodeLevel(current.level + 1, null)); // right
                }
            }
        }
        max = Math.max(max, count(tmp));
        return max;
    }

    private static int count(List<NodeLevel> list) {
        int count = 0;
        int idx = -1;
        for (int i = 0; i < list.size(); i++) {
            NodeLevel nodeLevel = list.get(i);
            if (nodeLevel.node != null) {
                if (idx == -1) {
                    count++;
                } else {
                    count += i - idx;
                }
                idx = i;
            }
        }
        return count;
    }

    private static int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height(node.left), height(node.right)) + 1;
    }

    private static class NodeLevel {
        private final int level;
        private final TreeNode node;

        public NodeLevel(int level, TreeNode node) {
            this.level = level;
            this.node = node;
        }

        @Override
        public String toString() {
            return "" + ((node == null) ? "null" : node.val);
        }
    }

    public static void main(String[] args) {
        Problem662 prob = new Problem662();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(9);
        System.out.println(prob.widthOfBinaryTree(root)); // 4

        root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        System.out.println(prob.widthOfBinaryTree(root)); // 2

        root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(5);
        root.right = new TreeNode(2);
        System.out.println(prob.widthOfBinaryTree(root)); // 2

        root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(5);
        root.left.left.left = new TreeNode(6);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(9);
        root.right.right.right = new TreeNode(7);
        System.out.println(prob.widthOfBinaryTree(root)); // 8
    }
}

@@ -453,43 +453,8 @@
  0;%0A
-        int height = height(root);%0A
     
@@ -541,16 +541,19 @@
 (1, root
+, 1
 ));%0A    
@@ -584,25 +584,23 @@
    List%3C
-NodeLevel
+Integer
 %3E tmp = 
@@ -916,57 +916,20 @@
 rent
-);%0A            if (current.level %3C height) %7B%0A    
+.position);%0A
     
@@ -972,36 +972,32 @@
                 
-    
 if (current.node
@@ -1025,36 +1025,32 @@
                 
-  
-  
 NodeLevel n = ne
@@ -1101,160 +1101,33 @@
 left
-);%0A                        queue.add(n);%0A                    %7D else %7B%0A                        NodeLevel n = new NodeLevel(current.level + 1, null);%0A    
+, 2 * current.position);%0A
     
@@ -1168,34 +1168,26 @@
             
-  
-  %7D%0A    
+%7D%0A
             
@@ -1216,36 +1216,32 @@
 ight != null) %7B%0A
-    
                 
@@ -1313,399 +1313,72 @@
 ight
-);%0A                        queue.add(n);%0A                    %7D else %7B%0A                        NodeLevel n = new NodeLevel(current.level + 1, null);%0A                        queue.add(n);%0A                    %7D%0A                %7D else %7B%0A                    queue.add(new NodeLevel(current.level + 1, null)); // left%0A                    queue.add(new NodeLevel(current.level + 1, null)); // right
+, (2 * current.position) + 1);%0A                    queue.add(n);
 %0A   
@@ -1518,25 +1518,23 @@
 nt(List%3C
-NodeLevel
+Integer
 %3E list) 
@@ -1547,571 +1547,53 @@
     
-int count = 0;%0A        int idx = -1;%0A        for (int i = 0; i %3C list.size(); i++) %7B%0A            NodeLevel nodeLevel = list.get(i);%0A            if (nodeLevel.node != null) %7B%0A                if (idx == -1) %7B%0A                    count++;%0A                %7D else %7B%0A                    count += i - idx;%0A                %7D%0A                idx = i;%0A            %7D%0A        %7D%0A        return count;%0A    %7D%0A%0A    private static int height(TreeNode node) %7B%0A        if (node == null) %7B%0A            return 0;%0A        %7D%0A        return Math.max(height(node.left), height(node.right)
+return list.get(list.size() - 1) - list.get(0
 ) + 
@@ -1709,17 +1709,16 @@
 e node;%0A
-%0A
         
@@ -1722,1439 +1722,212 @@
    p
-ublic NodeLevel(int level, TreeNode node) %7B%0A            this.level = level;%0A            this.node = node;%0A        %7D%0A%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + ((node == null) ? %22null%22 : node.val);%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem662 prob = new Problem662();%0A%0A        TreeNode root = new TreeNode(1);%0A        root.left = new TreeNode(3);%0A        root.left.left = new TreeNode(5);%0A        root.left.right = new TreeNode(3);%0A        root.right = new TreeNode(2);%0A        root.right.right = new TreeNode(9);%0A        System.out.println(prob.widthOfBinaryTree(root)); // 4%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(3);%0A        root.left.left = new TreeNode(5);%0A        root.left.right = new TreeNode(3);%0A        System.out.println(prob.widthOfBinaryTree(root)); // 2%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(3);%0A        root.left.left = new TreeNode(5);%0A        root.right = new TreeNode(2);%0A        System.out.println(prob.widthOfBinaryTree(root)); // 2%0A%0A        root = new TreeNode(1);%0A        root.left = new TreeNode(3);%0A        root.left.left = new TreeNode(5);%0A        root.left.left.left = new TreeNode(6);%0A        root.right = new TreeNode(2);%0A        root.right.right = new TreeNode(9);%0A        root.right.right.right = new TreeNode(7);%0A        System.out.println(prob.widthOfBinaryTree(root)); // 8
+rivate final int position;%0A%0A        public NodeLevel(int level, TreeNode node, int position) %7B%0A            this.level = level;%0A            this.node = node;%0A            this.position = position;%0A        %7D
 %0A   

Solve problem 662