# Another Solution with Topological Sort Idea - Time and Space Consuming

• The basic idea: build a graph reversely based on the tree (Reverse means if we have an edge a->b in tree, in graph, we have b->a) and calculate indegrees, then do topological sorting. It is time and space consuming.

``````
// My solution
public class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {

List<List<Integer>> res = new ArrayList<List<Integer>>();

// Build reverse graph and calculate indegrees
Map<TreeNode, Integer> indegrees = new HashMap<TreeNode, Integer>();
Map<TreeNode, Set<TreeNode>> graph = new HashMap<TreeNode, Set<TreeNode>>();
DFSHelper(indegrees, graph, root);

// Topological Sort
for (TreeNode node : indegrees.keySet()) {
if (indegrees.get(node) == 0)
queue.offer(node);
}
while(!queue.isEmpty()) {

for (TreeNode node: queue) {
}
int size = queue.size();
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
if (graph.containsKey(node)) {
for (TreeNode adj : graph.get(node)) {
if (indegrees.get(adj) - 1 == 0)
else
}
}

}
}
return res;
}

// Build the graph reversely and calculate indegrees
private void DFSHelper(Map<TreeNode, Integer> indegrees, Map<TreeNode, Set<TreeNode>> graph, TreeNode root) {
if (root == null)
return;
int val = root.val;
int count = 0;
if (root.left != null) {
++count;
if (!graph.containsKey(root.left.val)) {
graph.put(root.left, new HashSet<TreeNode>());
}
}
if (root.right != null) {
++count;
if (!graph.containsKey(root.right.val)) {
graph.put(root.right, new HashSet<TreeNode>());
}
}
if (!indegrees.containsKey(val)) {
indegrees.put(root, 0);
}
indegrees.put(root, count);

DFSHelper(indegrees, graph, root.left);
DFSHelper(indegrees, graph, root.right);
}

}

``````

• Brilliant thought of using topological sort for this problem.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.