leetcode113. 路径总和 II

举报
兔老大 发表于 2021/04/20 00:36:01 2021/04/20
【摘要】 113. 路径总和 II 难度中等163 给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5...

113. 路径总和 II

难度中等163

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22

 5 / \ 4   8 /   / \ 11  13  4 /  \ / \ 7 2  5   1

返回:

[ [5,4,11,2], [5,8,4,5]
]

思路:一个temp记录答案,符合条件就加入总答案记录,否则向左右尝试。


  
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. class Solution {
  11. List<List<Integer>> ans=new ArrayList<>();
  12. List<Integer> temp=new ArrayList<Integer>();
  13. public List<List<Integer>> pathSum(TreeNode root, int sum) {
  14. helper(root,sum);
  15. return ans;
  16. }
  17. public void helper(TreeNode root,int sum){
  18. if(root==null)return;
  19. temp.add(root.val);
  20. if(root.left==null && root.right==null && sum==root.val)
  21. ans.add(new ArrayList<>(temp));
  22. helper(root.left,sum-root.val);
  23. helper(root.right,sum-root.val);
  24. temp.remove(temp.size()-1);
  25. }
  26. }

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/104371575

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。