My Solution in Java, which takes 520 ms


  • 0
    G

    Hopefully you can get something from it and prompt some ideas to imporve it.

    import java.util.*;
    
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        //store all wanted paths
        private List<List<Integer>> paths = new ArrayList<List<Integer>>();
        
        //interface function, spends 520ms roughly
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            findPath(root, sum, 0, new LinkedList<Integer>());
            return paths;
        }
        
        //find all wanted paths and add them into 'paths' field one by one
        private void findPath(TreeNode root, int sum, int cur, LinkedList<Integer> path) {
            if (root != null) {
                path.addLast(root.val);
                cur += root.val;
                if (root.left == null && root.right == null && sum == cur) {
                    paths.add((List<Integer>) path.clone());
                }
                else {
                    if (root.left != null) {
                        findPath(root.left, sum, cur, path);
                        path.removeLast();
                    }
                    if (root.right != null) {
                        findPath(root.right, sum, cur, path);
                        path.removeLast();
                    }
                }
            }
        }
        
    }

Log in to reply
 

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