No tree modification, No Hashing, O(n) time, O(h) space


  • 0
    L

    Idea is depth first search, pass the result list(List<List<Integer>>) as parameter into the dfs function, do the following modification on the list:

    1. When traversing down the tree, add an empty list(List<Integer>) into the result set when the size of the result set is less than the current height of the tree.
    2. When backtracking, calculate the height of current node, then add it to the corresponding list(List<Integer>) we created in step 1.

    N: number of nodes
    H: height of the tree
    Time: O(N), Space: O(N)

    Code:

    public class Solution {
        public List<List<Integer>> findLeaves(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            dfs(list, root, 1);
            return list;
        }
        
        private int dfs(List<List<Integer>> traversal, TreeNode root, int level) {
            if (root == null) {
                return -1;
            }
            
            if (traversal.size() < level) {
                traversal.add(new ArrayList<>());
            }
            int l = dfs(traversal, root.left, level + 1);
            int r = dfs(traversal, root.right, level + 1);
            int index = Math.max(l, r) + 1;
            
            traversal.get(index).add(root.val);
            return index;
        }
    }
    

Log in to reply
 

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