LeetCode - Medium - 113. Path Sum II

爱被打了一巴掌 2022-10-06 03:57 150阅读 0赞

## Topic ##

*  Tree
 *  Depth-first Search

## Description ##

[https://leetcode.com/problems/path-sum-ii/][https_leetcode.com_problems_path-sum-ii]

Given the `root` of a binary tree and an integer `targetSum`, return all **root-to-leaf** paths where each path’s sum equals `targetSum`.

A **leaf** is a node with no children.

**Example 1:**

![abdc6911d9d9ee1b12dcdbb1945a1ab2.png][]

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
    Output: [[5,4,11,2],[5,8,4,5]]

**Example 2:**

![9bc801134935f549d425954a120f1cc3.png][]

Input: root = [1,2,3], targetSum = 5
    Output: []

**Example 3:**

Input: root = [1,2], targetSum = 0
    Output: []

**Constraints:**

*  The number of nodes in the tree is in the range `[0, 5000]`.
 *  `-1000 <= Node.val <= 1000`
 *  `-1000 <= targetSum <= 1000`

## Analysis ##

方法一：递归法

方法二：迭代法

## Submission ##

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class PathSumII { 
    	
    	//方法一：递归法
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) { 
            List<List<Integer>> result = new ArrayList<>();
        	pathSum(root, 0, targetSum, new ArrayList<>(), result);
        	return result;
        }
        
        private void pathSum(TreeNode node, int sum, int targetSum, List<Integer> path, List<List<Integer>> result) { 
        	if(node == null) return;
        	
        	path.add(node.val);
        	sum += node.val;
        	
        	if(node.left == null && node.right == null && sum == targetSum)
        		result.add(new ArrayList<>(path));
        	
        	pathSum(node.left, sum, targetSum, path, result);
        	pathSum(node.right, sum, targetSum, path, result);
        	
        	path.remove(path.size() - 1);
        }
        
        //方法二：迭代法
        @SuppressWarnings("unchecked")
    	public List<List<Integer>> pathSum2(TreeNode root, int targetSum) { 
        	List<List<Integer>> result = new ArrayList<>();
        	if(root == null) return result;
        	LinkedList<Object[]> stack = new LinkedList<>();
        	stack.push(new Object[] { root, 0, new ArrayList<>()});
        	
        	while(!stack.isEmpty()) { 
        		Object[] arr = stack.pop();
        		TreeNode node = (TreeNode)arr[0];
        		int sum = (int)arr[1];
        		List<Integer> path = (List<Integer>)arr[2];
        		
        		path.add(node.val);
        		sum += node.val;
        		
        		if(node.left == null && node.right == null) { 
        			if(sum == targetSum) 
        				result.add(path);
        		}else if(node.left != null && node.right == null) { 
        			stack.push(new Object[] { node.left, sum, path});
        		}else if(node.left == null && node.right != null) { 
        			stack.push(new Object[] { node.right, sum, path});
        		}else { 
        			stack.push(new Object[] { node.right, sum, new ArrayList<>(path)});
        			stack.push(new Object[] { node.left, sum, path});
        		}
        	}
        	return result;
        }
        
    }

## Test ##

import static org.junit.Assert.*;
    
    import java.util.Arrays;
    
    import org.hamcrest.collection.IsEmptyCollection;
    import org.hamcrest.collection.IsIterableContainingInAnyOrder;
    import org.junit.Test;
    
    import com.lun.util.BinaryTree;
    import com.lun.util.BinaryTree.TreeNode;
    
    public class PathSumIITest { 
    
    	@SuppressWarnings("unchecked")
    	@Test
    	public void test() { 
    		PathSumII obj = new PathSumII();
    
    		TreeNode root1 = BinaryTree.integers2BinaryTree(5,4,8,11,null,13,4,7,2,null,null,5,1);
    		assertThat(obj.pathSum(root1, 22), //
    				IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(5,4,11,2), Arrays.asList(5,8,4,5)));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3);
    		assertThat(obj.pathSum(root2, 5), IsEmptyCollection.empty());
    		
    		TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2);
    		assertThat(obj.pathSum(root3, 0), IsEmptyCollection.empty());
    		
    	}
    	
    	@Test
    	@SuppressWarnings("unchecked")
    	public void test2() { 
    		PathSumII obj = new PathSumII();
    		
    		TreeNode root1 = BinaryTree.integers2BinaryTree(5,4,8,11,null,13,4,7,2,null,null,5,1);
    		assertThat(obj.pathSum2(root1, 22), //
    				IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(5,4,11,2), Arrays.asList(5,8,4,5)));
    		
    		TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3);
    		assertThat(obj.pathSum2(root2, 5), IsEmptyCollection.empty());
    		
    		TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2);
    		assertThat(obj.pathSum2(root3, 0), IsEmptyCollection.empty());
    		
    	}
    	
    }

[https_leetcode.com_problems_path-sum-ii]: https://leetcode.com/problems/path-sum-ii/
[abdc6911d9d9ee1b12dcdbb1945a1ab2.png]: /images/20221005/fa8a2785c66243cd9f9884d2bb368d9f.png
[9bc801134935f549d425954a120f1cc3.png]: /images/20221005/dfb91d35df3d4452823fdac76d02a839.png