package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/find-bottom-left-tree-value/
 */
public class Problem513 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNodeLevel> queue = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        queue.add(new TreeNodeLevel(root, 1));
        int max = 0;
        while (!queue.isEmpty()) {
            TreeNodeLevel current = queue.remove();
            max = Math.max(max, current.level);
            if (!map.containsKey(current.level)) {
                List<Integer> list = new ArrayList<>();
                list.add(current.node.val);
                map.put(current.level, list);
            } else {
                map.get(current.level).add(current.node.val);
            }
            if (current.node.left != null) {
                queue.add(new TreeNodeLevel(current.node.left, current.level + 1));
            }
            if (current.node.right != null) {
                queue.add(new TreeNodeLevel(current.node.right, current.level + 1));
            }
        }
        return map.get(max).get(0);
    }

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

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

@@ -70,37 +70,8 @@
 ap;%0A
-import java.util.LinkedList;%0A
 impo
@@ -436,58 +436,31 @@
     
-LinkedList%3CTreeNodeLevel%3E queue = new LinkedList%3C%3E
+IntRef max = new IntRef
 ();%0A
@@ -530,159 +530,380 @@
     
-queue.add(new TreeNodeLevel(root, 1));%0A        int max = 0
+findBottomLeftValue(root, 1, max, map);%0A        return map.get(max.ref).get(0)
 ;%0A    
+%7D%0A%0A
     
-while (!queue.isEmpty()) %7B%0A            TreeNodeLevel current = queue.remove()
+private static class IntRef %7B%0A        private int ref;%0A    %7D%0A%0A    private static void findBottomLeftValue(TreeNode node, int level, IntRef max,%0A                                            Map%3CInteger, List%3CInteger%3E%3E map) %7B%0A        if (node == null) %7B%0A            return
 ;%0A    
+    %7D%0A
     
@@ -909,16 +909,20 @@
      max
+.ref
  = Math.
@@ -928,26 +928,22 @@
 .max(max
-, current.
+.ref, 
 level);%0A
@@ -946,28 +946,24 @@
 l);%0A        
-  
-  
 if (!map.con
@@ -971,24 +971,16 @@
 ainsKey(
-current.
 level)) 
@@ -977,28 +977,24 @@
 y(level)) %7B%0A
-    
             
@@ -1045,20 +1045,16 @@
         
-  
-  
 list.add
@@ -1050,32 +1050,24 @@
    list.add(
-current.
 node.val);%0A 
@@ -1081,20 +1081,16 @@
     
-    
 map.put(
 curr
@@ -1085,24 +1085,16 @@
 map.put(
-current.
 level, l
@@ -1107,20 +1107,16 @@
         
- 
-   
 %7D else %7B
@@ -1132,20 +1132,16 @@
     
-    
 map.get(
 curr
@@ -1136,24 +1136,16 @@
 map.get(
-current.
 level).a
@@ -1147,24 +1147,16 @@
 el).add(
-current.
 node.val
@@ -1170,111 +1170,38 @@
     
-    %7D%0A            if (current.node.left != null) %7B%0A                queue.add(new TreeNodeLevel(current.
+%7D%0A        findBottomLeftValue(
 node
@@ -1207,24 +1207,16 @@
 e.left, 
-current.
 level + 
@@ -1208,33 +1208,42 @@
 .left, level + 1
-)
+, max, map
 );%0A            %7D
@@ -1241,112 +1241,28 @@
     
-    %7D%0A            if (current.node.right != null) %7B%0A                queue.add(new TreeNodeLevel(current.
+findBottomLeftValue(
 node
@@ -1273,16 +1273,8 @@
 ht, 
-current.
 leve
@@ -1282,319 +1282,20 @@
  + 1
-));%0A            %7D%0A        %7D%0A        return map.get(max).get(0);%0A    %7D%0A%0A    private static class TreeNodeLevel %7B%0A        private final TreeNode node;%0A        private final int level;%0A%0A        public TreeNodeLevel(TreeNode node, int level) %7B%0A            this.node = node;%0A            this.level = level;%0A        %7D
+, max, map);
 %0A   

Update problem 513