首页 > 代码库 > Path Sum II
Path Sum II
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]]
这道题不是自己A出来的，看了discuss区里面的，不过写的的确漂亮
1 package com.gxf.test; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Stack; 6 7 8 9 class TreeNode {10 int val;11 TreeNode left;12 TreeNode right;13 TreeNode(int x) { val = x; }14 }15 16 public class Solution {17 public List<List<Integer>> pathSum(TreeNode root, int sum) {18 List<List<Integer>> result = new ArrayList<List<Integer>>();19 if(null == root)20 return result;21 if(null == root.left && null == root.right){ //叶子结点22 if(root.val == sum){23 List<Integer> element = new ArrayList<Integer>();24 element.add(sum);25 result.add(element);26 }27 }else{28 result = pathSum(root.left, sum - root.val); //获取左子树所有的路径29 List<List<Integer>> result_right = pathSum(root.right, sum - root.val);//获取右子树所有路径30 result.addAll(result_right);31 32 for(List<Integer> element : result){33 element.add(0, root.val); //将根节点添加到第一个位置34 }35 }36 37 return result;38 }39 }
另一种DFS
1 package com.gxf.test; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Stack; 6 7 8 9 class TreeNode {10 int val;11 TreeNode left;12 TreeNode right;13 TreeNode(int x) { val = x; }14 }15 16 public class Solution {17 public List<List<Integer>> pathSum(TreeNode root, int sum) {18 List<List<Integer>> result = new ArrayList<List<Integer>>();19 List<Integer> currentElement = new ArrayList<Integer>();20 21 getPath(root, sum, result, currentElement);22 23 return result;24 }25 26 /**27 * 递归获取result28 * @param root29 * @param sum30 * @param reuslt31 * @param currentResult32 */33 public void getPath(TreeNode root, int sum, List<List<Integer>> result, List<Integer> currentResult){34 if(null == root)35 return;36 currentResult.add(root.val); //添加到currentResult37 if(null == root.left && null == root.right){ //叶子结点38 if(sum == root.val){39 result.add(new ArrayList<Integer>(currentResult)); //添加到result中40 }41 currentResult.remove(currentResult.size() - 1); //移除叶子结点42 return ;43 }44 else{ //非叶子结点45 getPath(root.left, sum - root.val, result, currentResult); //遍历左子树46 getPath(root.right, sum - root.val, result, currentResult); //遍历右子树47 48 }49 50 currentResult.remove(currentResult.size() - 1); //递归回退时，没有这个只会删除叶子结点51 }52 }
Path Sum II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。