[LeetCode] 113. Path Sum II
[LeetCode] 113. Path Sum II
用户1148830
发布于 2018-01-03 17:45:57
发布于 2018-01-03 17:45:57
【原题】 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 1return
[
[5,4,11,2],
[5,8,4,5]
]【解释】 给定一颗二叉树和一个目标target，要求返回二叉树中从根节点到叶子结点的所有节点之和为target的路径。
【思路】 DFS的思想，若左右结点都遍历完之后，要将最后一个加入的结点删除，表示已经遍历过该节点所有的左右子女。
public class Solution {
public void pathSumCore(List<List<Integer>> results, List<Integer> result,int sum,TreeNode root){
if(root==null)
return;
result.add(root.val);
if(sum==root.val&&root.left==null&&root.right==null){
results.add(new ArrayList<>(result));
//result.remove(result.size()-1);
//return ;//这里若要返回的话， 必须加前面的删除前面加入的路径
}else{
if(root.left!=null)
pathSumCore(results,result,sum-root.val,root.left);
if(root.right!=null)
pathSumCore(results,result,sum-root.val,root.right);
}
result.remove(result.size()-1);//删除该结点
}
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<Integer> result=new ArrayList<Integer>();
List<List<Integer>> results=new ArrayList<List<Integer>>();
pathSumCore(results,result,sum,root);
return results;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年06月28日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读