My accepted Java solution [301 ms]


  • 0
    S
    public class Solution {
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            Stack<Integer> st=new Stack<Integer>();
            List<List<Integer>> l=new ArrayList<List<Integer>>();
            pathSum(root, sum, l, st);
            return l;
        }
        
        public void pathSum(TreeNode root, int sum, List<List<Integer>> l, Stack<Integer> st) {
            if(root==null) return;
            if(root.left==null && root.right==null ) {
                if(root.val-sum==0) {
                    st.push(root.val);
                    l.add(new ArrayList<Integer>());
                    for(int i:st) {
                        l.get(l.size()-1).add(i);
                    }
                    st.pop();
                }
            } else {
                st.push(root.val);
                pathSum(root.left,sum-root.val, l, st);
                pathSum(root.right,sum-root.val, l, st);
                st.pop();
            }
        }
    }

  • 0
    L

    As a minor improvement, one could replace the stack with a linked list which also supports fast push and pop operations.

    In this way, we could construct the result faster and more concise (in two lines):

    List<Integer> newPath = new LinkedList<Integer>();
    newPath.addAll(curPath);
    

Log in to reply
 

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