Clean Java solution (Accepted) without any helper recursive function


  • 68
    S

    Lot of recursive solutions on this forum involves creating a helper recursive function with added parameters. The added parameter which usually is of the type List<String> , carries the supplementary path information. However, the approach below doesn't use such a helper function.

    public List<String> binaryTreePaths(TreeNode root) {
            
            List<String> paths = new LinkedList<>();
    
            if(root == null) return paths;
            
            if(root.left == null && root.right == null){
                paths.add(root.val+"");
                return paths;
            }
    
             for (String path : binaryTreePaths(root.left)) {
                 paths.add(root.val + "->" + path);
             }
    
             for (String path : binaryTreePaths(root.right)) {
                 paths.add(root.val + "->" + path);
             }
    
             return paths;
            
        }

  • 2
    T

    The idea you give just makes believe you know recursive function so well. Very neat, way to go.


  • 8

    Neat solution. But I doubt the efficiency. In each recursion call, you do two unnecessary steps: (1) initialize a new LinkedList; (2) traverse again the children paths. The second bottleneck can be easily avoided.


  • 2
    H

    love the solution!! it's open my eyes....


  • -1
    Q

    I don't think it's a right solution. The list you return will be ["1"->"2"; "2"->"3"] rather than ["1" -> "2" -> "3"]


  • 1
    M

    you know recursive function really well. but this solution will use extra space to create new LinkedList at every recursion


  • 1

    haha, smart one. Too many array copying makes it slower when compared with other answers.

    But still, smart one. LOL


  • 0
    T

    Your code is neat and elegant, but the complexity is a little high. In a balanced binary tree(or maybe complete binary tree), time cost is O(n(logn)^2) and space cost is O(nlogn) while in a degenerative tree, namely a list, time cost is O(n^2) and space cost is O(n).


  • 1
    W

    I just what to say 66666!


  • 0

    @tomorrowch said in Clean Java solution (Accepted) without any helper recursive function:

    O(n(logn)^2) and space cost is O(nlogn)

    SPACE is actually O(N), not O(nlogn) deepest stack height is O(h)largest size of list is O(N)(N is larger than h)


  • 0
    A

    I had a similar approach, but didn't create a new list at every function call

    public List<String> binaryTreePaths(TreeNode root) {
            if (root == null)    return new ArrayList<>();       // return empty list
            
            if (root.left == null &&  root.right == null) {
                List<String> temp = new ArrayList<>();
                temp.add(root.val + "");
                return temp;                    // return list with only the leaf node
            }
            
            // First recursive call
            List<String> left = binaryTreePaths(root.left);
            for (int i = 0; i < left.size(); i++) {
                left.set(i, root.val + "->" + left.get(i));
            }        
            
            // Second recursive call
            List<String> right = binaryTreePaths(root.right);
            for (int i = 0; i < right.size(); i++) {
                right.set(i, root.val + "->" + right.get(i));
            }
            
            if (left.isEmpty() || right.isEmpty())    return left.isEmpty() ? right : left;
    
            left.addAll(right);         // Combine the two lists
            return left;                // Return combined list
        }
    

Log in to reply
 

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