Java solution, 1ms - Recursive depth-first search


  • 1
    A

    My first solution for this problem used a Queue, but it always seemed to be a bit slower. 1ms is the best I've been able to get, and using recursion seems to be more straightforward than a stack (though both are O(n) space). This solution just does a simple recursive in-order DFS and keeps track of the current depth, adding node values to the appropriate row's list (result.get(n) being the nth row).

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        helper(root, 0, result);
        return result;
    }
    public void helper(TreeNode root, int depth, List<List<Integer>> result) {
        if(root == null) return;
        helper(root.left, depth+1, result);
        while(result.size() <= depth) {
            result.add(new ArrayList<>());
        }
        result.get(depth).add(root.val);
        helper(root.right, depth+1, result);
    }
    

    I also noticed that the DFS doesn't have to be in-order. The two helper calls can be anywhere - putting them at the end makes the code a bit shorter since you can replace the while with an if, but I'm pretty sure it doesn't make it any faster. (Okay, if you want to get really technical, there might be a few operations saved in the compiled bytecode. I'm really not sure. I'd opt for the second solution though; it's a bit more straightforward. I'm leaving the first one for education's sake :P)

    public void helper(TreeNode root, int depth, List<List<Integer>> result) {
        if(root == null) return;
        if(result.size() <= depth) result.add(new ArrayList<>());
        result.get(depth).add(root.val);
        helper(root.left, depth+1, result);
        helper(root.right, depth+1, result);
    }

Log in to reply
 

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