[LeetCode]515. Find the maximum value in each tree row

subject

515.  Find the maximum in each tree row 
 Given the root node of a binary tree  root , Please find the maximum value of each layer in the binary tree .

 

 Example 1：



 Input : root = [1,3,2,5,3,null,9]
 Output : [1,3,9]
 Example 2：

 Input : root = [1,2,3]
 Output : [1,3]
 

 Tips ：

 The range of the number of nodes in a binary tree is  [0,104]
-231 <= Node.val <= 231 - 1
 

Method 1： Sequence traversal

public List<Integer> largestValues(TreeNode root) {
    
    List<Integer> res = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    if (root != null) q.offer(root);
    while (!q.isEmpty()) {
    
        int size = q.size();
        int t = Integer.MIN_VALUE;
        for (int i = 0; i < size; i++) {
    
            TreeNode cur = q.poll();
            t = Math.max(t, cur.val);
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        res.add(t);
    }
    return res;
}

Method 2：DFS

       public List<Integer> largestValues(TreeNode root) {
    
            List<Integer> res = new ArrayList<>();
            if (root == null) return res;
            dfs(root, 0, res);
            return res;
        }

        //depth Table the depth of the currently processed node 
        private void dfs(TreeNode root, int depth, List<Integer> res) {
    
            if (depth == res.size()) {
    // The node that first came to this depth 
                res.add(root.val);
            } else {
    // Not the first time to this floor 
                res.set(depth, Math.max(root.val, res.get(depth)));
            }
            if (root.left != null) dfs(root.left, depth + 1, res);
            if (root.right != null) dfs(root.right, depth + 1, res);
        }