09/14

surajr · surajr · commit 36a9770150ad · 2017-09-14T19:10:45.000-07:00
diff --git a/README.md b/README.md
@@ -72,6 +72,7 @@ Feel free to add issues, comment and pull request.
 | Leetcode  | [637. Average of Levels in Binary Tree](https://leetcode.com/problems/average-of-levels-in-binary-tree/description/) | [Java](./java/averageOfLevels.java) \| [Python](./Python/) | _O(n)_       | _O(1)_          |  Easy       |         |
 | Leetcode  | [663. Equal Tree Partition](https://leetcode.com/problems/equal-tree-partition/description/) | [Java](./java/CheckEqualTrees.java) \| [Python](./Python/) |        |           |  Medium       |         |
 | Leetcode  | [623. Add One Row to Tree](https://leetcode.com/problems/add-one-row-to-tree/description/) | [Java](./java/addOneRow.java) \| [Python](./Python/) |        |           |  Medium       |         |
+| Leetcode  | [662. Maximum Width of Binary Tree](https://leetcode.com/problems/maximum-width-of-binary-tree/description/) | [Java](./java/widthOfBinaryTree.java) \| [Python](./Python/) |   O(n)     |   O(d)        |  Medium       |         |
 
 
 ## Dynamic Programming
diff --git a/java/widthOfBinaryTree.java b/java/widthOfBinaryTree.java
@@ -0,0 +1,57 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+
+
+/*
+    use a travel traversal template, use another queue to keep the index of each level nodes. left node index = this node index * 2, right =     this node index*2 + 1. the width should be the last node index - first node index + 1
+
+*/
+class Solution {
+    public int widthOfBinaryTree(TreeNode root) {
+        if(root == null) return 0;
+        Queue<TreeNode> queue = new ArrayDeque<>();
+        Queue<Integer> count = new ArrayDeque<>();
+        int max = 1;
+        
+        queue.offer(root);
+        count.offer(1);
+        
+        while(!queue.isEmpty())
+        {
+            int size = queue.size();            
+            int left = 0;
+            int right = 0;
+            
+            for(int i=0; i<size; i++)
+            {
+                TreeNode node = queue.poll();
+                int index = count.poll();
+                if(i==0) left = index;
+                if(i==size-1) right = index;
+                
+                if(node.left != null)
+                {
+                    queue.offer(node.left);
+                    count.offer(index*2);
+                }
+                
+                if(node.right != null)
+                {
+                    queue.offer(node.right);
+                    count.offer(index*2+1);
+                }
+            }
+            
+            max = Math.max(max, right - left+1);
+        }
+        
+        return max;
+    }
+}
