LeetCode - Medium - 113. Path Sum II

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

Topic

  • Tree
  • Depth-first Search

Description

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

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

Example 2:

9bc801134935f549d425954a120f1cc3.png

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

Example 3:

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

Constraints:

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

Analysis

方法一:递归法

方法二:迭代法

Submission

  1. import java.util.ArrayList;
  2. import java.util.LinkedList;
  3. import java.util.List;
  4. import com.lun.util.BinaryTree.TreeNode;
  5. public class PathSumII {
  6. //方法一:递归法
  7. public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
  8. List<List<Integer>> result = new ArrayList<>();
  9. pathSum(root, 0, targetSum, new ArrayList<>(), result);
  10. return result;
  11. }
  12. private void pathSum(TreeNode node, int sum, int targetSum, List<Integer> path, List<List<Integer>> result) {
  13. if(node == null) return;
  14. path.add(node.val);
  15. sum += node.val;
  16. if(node.left == null && node.right == null && sum == targetSum)
  17. result.add(new ArrayList<>(path));
  18. pathSum(node.left, sum, targetSum, path, result);
  19. pathSum(node.right, sum, targetSum, path, result);
  20. path.remove(path.size() - 1);
  21. }
  22. //方法二:迭代法
  23. @SuppressWarnings("unchecked")
  24. public List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
  25. List<List<Integer>> result = new ArrayList<>();
  26. if(root == null) return result;
  27. LinkedList<Object[]> stack = new LinkedList<>();
  28. stack.push(new Object[] { root, 0, new ArrayList<>()});
  29. while(!stack.isEmpty()) {
  30. Object[] arr = stack.pop();
  31. TreeNode node = (TreeNode)arr[0];
  32. int sum = (int)arr[1];
  33. List<Integer> path = (List<Integer>)arr[2];
  34. path.add(node.val);
  35. sum += node.val;
  36. if(node.left == null && node.right == null) {
  37. if(sum == targetSum)
  38. result.add(path);
  39. }else if(node.left != null && node.right == null) {
  40. stack.push(new Object[] { node.left, sum, path});
  41. }else if(node.left == null && node.right != null) {
  42. stack.push(new Object[] { node.right, sum, path});
  43. }else {
  44. stack.push(new Object[] { node.right, sum, new ArrayList<>(path)});
  45. stack.push(new Object[] { node.left, sum, path});
  46. }
  47. }
  48. return result;
  49. }
  50. }

Test

  1. import static org.junit.Assert.*;
  2. import java.util.Arrays;
  3. import org.hamcrest.collection.IsEmptyCollection;
  4. import org.hamcrest.collection.IsIterableContainingInAnyOrder;
  5. import org.junit.Test;
  6. import com.lun.util.BinaryTree;
  7. import com.lun.util.BinaryTree.TreeNode;
  8. public class PathSumIITest {
  9. @SuppressWarnings("unchecked")
  10. @Test
  11. public void test() {
  12. PathSumII obj = new PathSumII();
  13. TreeNode root1 = BinaryTree.integers2BinaryTree(5,4,8,11,null,13,4,7,2,null,null,5,1);
  14. assertThat(obj.pathSum(root1, 22), //
  15. IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(5,4,11,2), Arrays.asList(5,8,4,5)));
  16. TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3);
  17. assertThat(obj.pathSum(root2, 5), IsEmptyCollection.empty());
  18. TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2);
  19. assertThat(obj.pathSum(root3, 0), IsEmptyCollection.empty());
  20. }
  21. @Test
  22. @SuppressWarnings("unchecked")
  23. public void test2() {
  24. PathSumII obj = new PathSumII();
  25. TreeNode root1 = BinaryTree.integers2BinaryTree(5,4,8,11,null,13,4,7,2,null,null,5,1);
  26. assertThat(obj.pathSum2(root1, 22), //
  27. IsIterableContainingInAnyOrder.containsInAnyOrder(Arrays.asList(5,4,11,2), Arrays.asList(5,8,4,5)));
  28. TreeNode root2 = BinaryTree.integers2BinaryTree(1, 2, 3);
  29. assertThat(obj.pathSum2(root2, 5), IsEmptyCollection.empty());
  30. TreeNode root3 = BinaryTree.integers2BinaryTree(1, 2);
  31. assertThat(obj.pathSum2(root3, 0), IsEmptyCollection.empty());
  32. }
  33. }

发表评论

表情:
评论列表 (有 0 条评论,280人围观)

还没有评论,来说两句吧...

相关阅读