pre-order DFS with level

102. Binary Tree Level Order Traversal

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        dfs(result, root, 0);
        return result;
    }
    
    public void dfs(List<List<Integer>> result, TreeNode root, int level) {
        if (root == null) return;
        if (level == result.size()) {
            result.add(new LinkedList<Integer>());
        }
        result.get(level).add(root.val);
        dfs(result, root.left, level+1);
        dfs(result, root.right, level+1);
    }
}

103. Binary Tree Zigzag Level Order Traversal

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        dfs(result, root, 0);
        return result;
    }
    
    public void dfs(List<List<Integer>> result, TreeNode root, int level) {
        if (root == null) return;
        if (level == result.size()) {
            result.add(new LinkedList<Integer>());
        }
        List<Integer> list = result.get(level);
        if(level % 2 == 0) list.add(root.val);
        else list.add(0, root.val);
           
        dfs(result, root.left, level + 1);
        dfs(result, root.right, level + 1);
    }
}

515. Find Largest Value in Each Tree Row

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);
    }
}