首页 > 代码库 > LeetCode Path Sum II
LeetCode Path Sum II
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]]
方法1：只要在每个树节点中加入一个父节点，就可以用上一题的解法了。
方法2：dfs
方法1的代码：
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 12 class TreeNodePlus {13 TreeNode node;14 TreeNodePlus father;15 TreeNodePlus(TreeNode x,TreeNodePlus f) {16 node=x;17 father=f;18 }19 }20 21 List<List<Integer>> paths = new ArrayList<List<Integer>>();22 23 public List<List<Integer>> pathSum(TreeNode root, int sum) {24 TreeNodePlus newRoot = new TreeNodePlus(root, null);25 hasPathSum(newRoot, sum);26 return paths;27 }28 29 public void hasPathSum(TreeNodePlus root, int sum){30 if (root.node == null) {31 return ;32 }33 if (root.node.val==sum && root.node.left==null && root.node.right==null) {34 ArrayList<Integer> list = new ArrayList<Integer>();35 TreeNodePlus father = root;36 while (father != null) {37 list.add(0,father.node.val);38 father = father.father;39 40 }41 paths.add(list);42 return;43 }44 45 hasPathSum(new TreeNodePlus(root.node.left,root), sum-root.node.val) ;46 hasPathSum(new TreeNodePlus(root.node.right,root), sum-root.node.val);47 }48 49 }
方法2的代码
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 12 13 14 List<List<Integer>> paths = new ArrayList<List<Integer>>();15 public List<List<Integer>> pathSum(TreeNode root, int sum) {16 17 List<Integer> list = new ArrayList<Integer>();18 dfs(root, sum, 0, list);19 return paths;20 }21 void dfs(TreeNode root, int sum, int curr, List<Integer> list) {22 if (root == null) {23 return;24 }25 26 if (root.left == null && root.right == null) {27 if (curr + root.val == sum) {28 list.add(root.val);29 paths.add(list);30 31 }32 return;33 }34 35 list.add(root.val);36 dfs(root.left, sum, curr + root.val, new ArrayList<Integer>(list));37 38 dfs(root.right, sum, curr + root.val, new ArrayList<Integer>(list));39 }40 41 }
LeetCode Path Sum II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。