You need to find the largest value in each row of a binary tree.
Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

Solution1：DFS

深度优先，建立一个result linked数组，index(level)上存的就是当前index(level) 行的Max值，linked数组随着level扩大
Time Complexity: O(N) Space Complexity: O(n) worst缓存

Solution2：BFS

广度优先，queue实现，queue中每一组就是一个level中的元素，找出最大依行存下
Time Complexity: O(N) Space Complexity: O(n) worst缓存

Solution1 Code：

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        dfs(root, result, 0);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result, int level) {
        if(node == null) {
            return;
        }
        
        if(level == result.size()) {
            // expand result list to next level
            result.add(node.val);
        } 
        else { 
            // update max
            result.set(level, Math.max(result.get(level), node.val));
        }
        dfs(node.left, result, level + 1);
        dfs(node.right, result, level + 1);
    }
}

Solution2 Code：

class Solution {
    //BFS 最要在Node进入queue前就进行非空判断，使得进入queue的node本身都非null
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> result = new LinkedList<Integer>();
        
        if(root == null) return result;
        
        queue.offer(root);
        while(!queue.isEmpty()) {
            int largest_elem = Integer.MIN_VALUE;
            int num_on_level = queue.size();
            for(int i = 0; i < num_on_level; i++) {
                TreeNode cur = queue.poll();
                largest_elem = Math.max(largest_elem, cur.val);
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            result.add(largest_elem);
        }
        
        return result;
    }
}