Another Solution with Topological Sort Idea - Time and Space Consuming


  • 0
    A

    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
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            for (TreeNode node : indegrees.keySet()) {
                if (indegrees.get(node) == 0)
                    queue.offer(node);
            }
            while(!queue.isEmpty()) {
    
                res.add(new ArrayList<Integer>());
                for (TreeNode node: queue) {
                    res.get(res.size() - 1).add(node.val);
                }
                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)
                                queue.offer(adj);
                            else
                                indegrees.put(adj, indegrees.get(adj) - 1);
                        }
                    }
    
                }
            }
            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>());
                    graph.get(root.left).add(root);
                }
            }
            if (root.right != null) {
                ++count;
                if (!graph.containsKey(root.right.val)) {
                    graph.put(root.right, new HashSet<TreeNode>());
                    graph.get(root.right).add(root);
                }
            }
            if (!indegrees.containsKey(val)) {
                indegrees.put(root, 0);
            }
            indegrees.put(root, count);
    
            DFSHelper(indegrees, graph, root.left);
            DFSHelper(indegrees, graph, root.right);
        }
       
    }
    
    
    
    

  • 0
    V

    Brilliant thought of using topological sort for this problem.


Log in to reply
 

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