My Java solution with DFS, BFS and recursion


  • 0
    C

    recursion:

    public class Solution {
        //pre order
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> list=new ArrayList<List<Integer>>();
            
            makeList(list,root,new ArrayList<Integer>(),sum);
            return list;
        }
        
        private void makeList(List<List<Integer>> list, TreeNode node, List<Integer> path, int sum) {
            if (node==null) return;
            path.add(node.val);
            if (node.left==null && node.right==null && node.val==sum) {
                list.add(path);
                return;
            }
            makeList(list, node.left, new ArrayList<Integer>(path),sum-node.val);
            makeList(list, node.right, new ArrayList<Integer>(path),sum-node.val);
        }
    }
    

    DFS - stack:

    public class Solution {
        //DFS - Stack
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> list=new ArrayList<List<Integer>>();
            Queue<TreeNode> qNode=new LinkedList<TreeNode>();
            Queue<Integer> qSum=new LinkedList<Integer>();
            Queue<List<Integer>> qList=new LinkedList<List<Integer>>();
            
            if (root==null) return list;
            qNode.add(root);
            qSum.add(sum);
            qList.add(new LinkedList<Integer>());
            
            while (!qNode.isEmpty()) {
                TreeNode curNode=qNode.remove();
                int curSum=qSum.remove();
                List<Integer> curList=qList.remove();
                
                curList.add(curNode.val);
                
                if (curNode.left==null && curNode.right==null && curNode.val==curSum) 
                    list.add(new LinkedList<Integer>(curList));
                if (curNode.left!=null) {
                    qNode.add(curNode.left);
                    qSum.add(curSum-curNode.val);
                    qList.add(new LinkedList<Integer>(curList));
                }
                if (curNode.right!=null) {
                    qNode.add(curNode.right);
                    qSum.add(curSum-curNode.val);
                    qList.add(new LinkedList<Integer>(curList));
                }
            }
            return list;
        }
    
    }
    

    BFS - queue

    public class Solution {
        //BFS - queue
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            List<List<Integer>> list=new ArrayList<List<Integer>>();
            Queue<TreeNode> qNode=new LinkedList<TreeNode>();
            Queue<Integer> qSum=new LinkedList<Integer>();
            Queue<List<Integer>> qList=new LinkedList<List<Integer>>();
            
            if (root==null) return list;
            qNode.add(root);
            qSum.add(sum);
            qList.add(new LinkedList<Integer>());
            
            while (!qNode.isEmpty()) {
                TreeNode curNode=qNode.remove();
                int curSum=qSum.remove();
                List<Integer> curList=qList.remove();
                
                curList.add(curNode.val);
                
                if (curNode.left==null && curNode.right==null && curNode.val==curSum) 
                    list.add(new LinkedList<Integer>(curList));
                if (curNode.left!=null) {
                    qNode.add(curNode.left);
                    qSum.add(curSum-curNode.val);
                    qList.add(new LinkedList<Integer>(curList));
                }
                if (curNode.right!=null) {
                    qNode.add(curNode.right);
                    qSum.add(curSum-curNode.val);
                    qList.add(new LinkedList<Integer>(curList));
                }
            }
            return list;
        }
    
    }

Log in to reply
 

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