摘要：题目要求从树中找到所有符合条件的从根节点到叶节点路径，条件即为树上所有节点值的和等于目标值。可以参考这篇博客思路和代码其实这里本质上的思路并没有改变，还是采用深度优先算法，采用自顶向下递归的方式将符合条件的结果放入结果集中。
题目要求
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]
]
从树中找到所有符合条件的从根节点到叶节点路径，条件即为树上所有节点值的和等于目标值。
Path Sum I可以参考这篇博客
思路和代码
其实这里本质上的思路并没有改变，还是采用深度优先算法，采用自顶向下递归的方式将符合条件的结果放入结果集中。
public List> pathSum(TreeNode root, int sum) {
List> result = new ArrayList>();
pathSum(root, sum, new ArrayList(), result);
return result;
}
public void pathSum(TreeNode root, int sum, List path, List> result){
if(root==null) return;
sum -= root.val;
if(isLeaf(root) && sum==0){
path.add(root.val);
result.add(new ArrayList(path));
path.remove(path.size()-1);
return;
}
path.add(root.val);
pathSum(root.left, sum, path, result);
pathSum(root.right, sum, path, result);
path.remove(path.size()-1);
}
private boolean isLeaf(TreeNode node){
return node!=null && node.left==null && node.right==null;
}
想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67384.html
