Very Concise Java solution with NO helper class


  • 0
    M

    Here is my very concise Java solution without using any helper class.

    The idea is rather simple. Using an ArrayList called "stem" to remember the value while going down the tree.

    Reducing the sum with the value of each node, and checking sum value when hitting the leaf nodes.
    If the sum equals to zero, makes a copy out of "stem", adds the copy to result ArrayList, and returns the result.

    Remember to Add the value of current node to "stem" before checking it's two leaves, and remove it afterword.

    I think this idea is better than the lazy "stem" solution, which populates each element in the result List<List<Integer>> after the sum paths are found.

    public class Solution {

    List<Integer> stem = new ArrayList<Integer>();
    List<List<Integer>> ret = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
         
        if(root == null) return ret;
    
        if(sum == root.val && root.left == null && root.right == null){
            ArrayList<Integer> copy = new ArrayList<Integer>(stem);
            copy.add(root.val);
            ret.add(copy);
            return ret;
            //return ret.add(copy);
        }
        sum -= root.val;
        stem.add(root.val);
        pathSum(root.left,sum); 
        pathSum(root.right,sum);
        stem.remove(stem.size()-1);
    
        return ret;
    }
    

    }


Log in to reply
 

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