366 Find Leaves of Binary Tree

366. Find Leaves of Binary Tree

1. Question

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example: Given binary tree

          1
         / \
        2   3
       / \     
      4   5

Returns[4, 5, 3], [2], [1].

Explanation:

1. Removing the leaves[4, 5, 3]would result in this tree:

          1
         / 
        2

1. Now removing the leaf[2]would result in this tree:

          1

1. Now removing the leaf[1]would result in the empty tree:

          []

Returns[4, 5, 3], [2], [1].

2. Implementation

(1) DFS

思路: 对于每个node，找到它相应的高度，并根据这个高度加到相应的res里。leaves的那一层会在level 0。

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        recFindLeaves(root, res);
        return res;
    }

    public int recFindLeaves(TreeNode node, List<List<Integer>> res) {
        if (node == null) {
            return 0;
        }

        int leftLevel = recFindLeaves(node.left, res);
        int rightLevel = recFindLeaves(node.right, res);
        int level = Math.max(leftLevel, rightLevel) + 1;

        if (res.size() < level) {
            res.add(new ArrayList<>());
        }
        res.get(level - 1).add(node.val);
        return level;
    }
}

3. Time & Space Complexity

DFS: 时间复杂度: O(n), 空间复杂度: O(n)