# Question

Formatted question description: https://leetcode.ca/all/366.html

 366	Find Leaves of Binary Tree

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:

Input: [1,2,3,4,5]

1
/ \
2   3
/ \
4   5

Output: [[4,5,3],,]

Explanation:

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

1
/
2

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

1

3. Now removing the leaf  would result in the empty tree:

[]

@tag-tree


# Algorithm

Each node is separated from the left child node and the right child node to get two depths,

Since the condition of becoming a leaf node is that the left and right child nodes are empty, we take the larger value of the left and right child nodes plus 1 as the depth value of the current node.

Knowing the depth value, you can add the node value to the correct position in the result.

# Code

Java

• import java.util.ArrayList;
import java.util.List;

public class Find_Leaves_of_Binary_Tree {

public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
helper(result, root);
return result;
}

// traverse the tree bottom-up recursively
private int helper(List<List<Integer>> list, TreeNode root) {
if (root == null) {
return -1; // @note: +1==0, mapping to list index
}

int left = helper(list, root.left);
int right = helper(list, root.right);
int currentDepthFromBottom = Math.max(left, right) + 1;

// the first time this code is reached is when curr==0,
// since the tree is bottom-up processed.
if (list.size() <= currentDepthFromBottom) {
}

return currentDepthFromBottom;
}
}

• // OJ: https://leetcode.com/problems/find-leaves-of-binary-tree/
// Time: O(N)
// Space: O(H)
class Solution {
private:
bool dfs(TreeNode *root, vector<int> &v) {
if (!root) return true;
if (!root->left && !root->right) {
v.push_back(root->val);
return true;
}
if (dfs(root->left, v)) root->left = NULL;
if (dfs(root->right, v)) root->right = NULL;
return false;
}
vector<int> removeLeaves(TreeNode *root) {
vector<int> v;
dfs(root, v);
return v;
}
public:
vector<vector<int>> findLeaves(TreeNode* root) {
if (!root) return {};
vector<vector<int>> ans;
while (root->left || root->right) {
ans.push_back(removeLeaves(root));
}
ans.push_back({ root->val });
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections

class Solution(object):
def findLeaves(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""

def helper(p, res):
if not p:
return 0
left = helper(p.left, res)
right = helper(p.right, res)
depth = max(left, right) + 1
res[depth].append(p.val)
return depth

ans = []
res = collections.defaultdict(list)
helper(root, res)
for i in range(1, len(res) + 1):
ans.append(res[i])
return ans