Easy Java DFS solution, 3ms


  • 0
    Y
    public class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            //10:07am - 10:21am
            // DFS to propogate a root to leaf list, and check at the leaf node
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            pathSumHelper(root, new ArrayList<Integer>(), sum, result);
            return result;
        }
        
        private void pathSumHelper(TreeNode root, List<Integer> prefix, int sum, List<List<Integer>> result) {
            // base case of DFS
            if (root == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                if (sum == root.val) {
                    prefix.add(root.val);
                    result.add(new ArrayList<Integer>(prefix));
                    prefix.remove(prefix.size()-1);
                }
                return;
            }
            // recursion
            prefix.add(root.val);
            if (root.left != null) {
                pathSumHelper(root.left, prefix, sum - root.val, result);
            }
            if (root.right != null) {
                pathSumHelper(root.right, prefix, sum - root.val, result);
            }
            prefix.remove(prefix.size()-1);
        }
    }

  • 1
    Y

    I slightly simplified you code:

    public class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (root == null) return result;
            helper(root, new ArrayList<Integer>(), sum, result);
            return result;
        }
        
        public void helper(TreeNode root, List<Integer> path, int remain, List<List<Integer>> result) {
            if (root == null) return;
            path.add(root.val);
            if (root.left == null && root.right == null && root.val == remain) {
                result.add(new ArrayList<Integer>(path));
            }
            helper(root.left, path, remain - root.val, result);
            helper(root.right, path, remain - root.val, result);
            path.remove(path.size() - 1);
        }
    }

  • 0
    Y

    Thanks! It makes the code much more elegant! You were able to think from a higher level of abstraction in that:

    1. the (root == null) check makes the null check for root.left and root.right unnecessary;
    2. state is re-installed at the breaking point, therefore, just one pair of "path.add(root.val);" and "path.remove(path.size() - 1);" is necessary, at the beginning and end of the function.

    very smart. thanks!


  • 0
    Z

    @Yuansam why write" path.remove(path.size() - 1);"


  • 0
    H

    @Yuansam I like how you reduced one param by not passing a temporary sum but subtracting from sum.


Log in to reply
 

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