0366. Find Leaves of Binary Tree

https://leetcode.com/problems/find-leaves-of-binary-tree

Description

Given the root of a binary tree, collect a tree's nodes as if you were doing this:

• Collect all the leaf nodes.

• Remove all the leaf nodes.

• Repeat until the tree is empty.

Example 1:

**Input:** root = [1,2,3,4,5]
**Output:** [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

Example 2:

**Input:** root = [1]
**Output:** [[1]]

Constraints:

• The number of nodes in the tree is in the range [1, 100].

• -100 <= Node.val <= 100

ac

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        dfs(root, map);

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 1; i <= map.size(); i++) {
            res.add(map.get(i));
        }

        return res;
    }

    public int dfs(TreeNode node, Map<Integer, List<Integer>> map) {
        if (node == null) return 0;

        int left = dfs(node.left, map);
        int right = dfs(node.right, map);

        int dist = Math.max(left, right) + 1;
        map.putIfAbsent(dist, new ArrayList<>());
        map.get(dist).add(node.val);

        return dist;
    }
}

/*
1) dfs get distance to leaf, store in map; 2) iterate map, get result
*/