LeetCode - Path Sum II


LeetCode - Path Sum
Related: LeetCode 437 - Path Sum III
LeetCode - Path Sum II | Darren's Blog
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]
add a node to the list
recur its left child and right child
remove this node from the list before backtracking (previous condition would be restored)
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null)
            return result;
        recursivePathSum(root, sum, new ArrayList<Integer>(), result);
        return result;
    }
    private void recursivePathSum(TreeNode root, int sum, ArrayList<Integer> current,
                                  ArrayList<ArrayList<Integer>> result) {
        if (root == null)   // Empty tree
            return;
        // It is a leaf and its value is the path sum
        if (root.val == sum && root.left == null && root.right == null) {
            // Add the node into the current path, and store that path before recover the path
            current.add(root.val);
            result.add(new ArrayList<Integer>(current));
            current.remove(current.size()-1);//
            return;
        }
        // Add the node into the current path, and explore its left subtree and right subtree
        // before recover the path
        current.add(root.val);
        recursivePathSum(root.left, sum-root.val, current, result);
        recursivePathSum(root.right, sum-root.val, current, result);
        current.remove(current.size()-1);
    }
Recursive like the Question 66, just use a vector<int> to store the result.
Just don't forget the backtracking.
After searching the left node and right node, DO NOT forget to pop the node added in the vector.
Ideas see Question 66.
Details see code below:
Java Code From: http://rleetcode.blogspot.com/2014/02/path-sum-ii-java.html
https://leetcode.com/discuss/16980/dfs-with-one-linkedlist-accepted-java-solution
Using ArrayList as a stack
public List<List<Integer>> pathSum(TreeNode root, int sum){
 List<List<Integer>> result  = new LinkedList<List<Integer>>();
 List<Integer> currentResult  = new LinkedList<Integer>();
 pathSum(root,sum,currentResult,result);
 return result;
}

public void pathSum(TreeNode root, int sum, List<Integer> currentResult,
  List<List<Integer>> result) {

 if (root == null)
  return;
 currentResult.add(new Integer(root.val));
 if (root.left == null && root.right == null && sum == root.val) {
  result.add(new LinkedList(currentResult));
  currentResult.remove(currentResult.size() - 1);//don't forget to remove the last integer
  return;
 } else {
  pathSum(root.left, sum - root.val, currentResult, result);
  pathSum(root.right, sum - root.val, currentResult, result);
 }
 currentResult.remove(currentResult.size() - 1);
}
https://leetcode.com/discuss/76870/my-simple-java-solution
Previous one is better, this creates two many lists that are not valid answers.
private List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { helper(new ArrayList<Integer>(), root, sum); return result; } private void helper(List<Integer> list, TreeNode root, int sum) { if (root == null) return; list.add(root.val); sum -= root.val; if (root.left == null && root.right == null) { if (sum == 0) result.add(list); return; } helper(new ArrayList<Integer>(list), root.left, sum); helper(new ArrayList<Integer>(list), root.right, sum); }
http://www.jiuzhang.com/solutions/path-sum-ii/
https://discuss.leetcode.com/topic/13657/simple-dfs-java-solution
    private List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    
    public void pathSumInner(TreeNode root, int sum, Stack<Integer>path) {
        path.push(root.val);
        if(root.left == null && root.right == null)
            if(sum == root.val) resultList.add(new ArrayList<Integer>(path));
        if(root.left!=null) pathSumInner(root.left, sum-root.val, path);
        if(root.right!=null)pathSumInner(root.right, sum-root.val, path);
        path.pop();
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null) return resultList;
        Stack<Integer> path = new Stack<Integer>();
        pathSumInner(root, sum, path);
        return resultList;
    }
http://www.jyuan92.com/blog/leetcode-path-sum-ii/
public List<List<Integer>> pathSum(TreeNode root, int sum) {
   List<List<Integer>> res = new ArrayList<List<Integer>>();
   helper(root, res, new ArrayList<Integer>(), sum);
   return res;
}
private void helper(TreeNode root, List<List<Integer>> res, List<Integer> temp, int sum) {
   if (null == root) {
       return;
   }
   temp.add(root.val);
   if (null == root.left && null == root.right && sum == root.val) {
       res.add(new ArrayList<Integer>(temp));
   }
   helper(root.left, res, temp, sum - root.val);
   helper(root.right, res, temp, sum - root.val);
   temp.remove(temp.size() - 1);
}
X. Not easy to understand
https://leetcode.com/discuss/12699/my-accepted-java-solution
public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> pathList = new ArrayList<List<Integer>>(); if(root==null){ return pathList; } if(root.left==null&&root.right==null){//if find a path, create a new list and add to the pathList. if(root.val==sum){ List<Integer> list = new ArrayList<Integer>(); list.add(root.val); pathList.add(list); } return pathList; } //find path left and right child and merge two list together. pathList = pathSum(root.left, sum-root.val); List<List<Integer>> pathList_right = pathSum(root.right, sum-root.val); for(List<Integer> l:pathList_right){ pathList.add(l); } //add current root to every list in path list. for(List<Integer> l:pathList){ l.add(0, root.val); } return pathList; }

https://github.com/rffffffff007/leetcode/blob/master/Path%20Sum%20II.java
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        pathSum(root, sum, res, new ArrayList<Integer>());
        return res;
    }
 
    private void pathSum(TreeNode root, int sum, ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list){
        if(root == null)
            return;
        list.add(root.val);
        sum -= root.val;
        if(root.left == null && root.right == null && sum == 0)
            res.add(new ArrayList<Integer>(list));
        else{
            pathSum(root.left, sum, res, list);
            pathSum(root.right, sum, res, list);
        }
        list.remove(list.size() - 1);
    }
http://www.programcreek.com/2014/05/leetcode-path-sum-ii-java/
Code is cleaner if we check null as base case: as we just need check once.
public List<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if(root == null) 
        return result;
 
    ArrayList<Integer> l = new ArrayList<Integer>();
    l.add(root.val);
    dfs(root, sum-root.val, result, l);
    return result;
}
 
public void dfs(TreeNode t, int sum, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> l){
    if(t.left==null && t.right==null && sum==0){
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.addAll(l);
        result.add(temp);
    }
 
    //search path of left node
    if(t.left != null){
        l.add(t.left.val);
        dfs(t.left, sum-t.left.val, result, l);
        l.remove(l.size()-1);
    }
 
    //search path of right node
    if(t.right!=null){
        l.add(t.right.val);
        dfs(t.right, sum-t.right.val, result, l);
        l.remove(l.size()-1);
    }
}
http://blog.sina.com.cn/s/blog_6db692830102v0oe.html
Read full article from LeetCode - Path Sum II | Darren's Blog

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts