内容简介:题目地址:题目描述:
题目地址:
https://leetcode-cn.com/probl...
题目描述:
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22,
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
解答:
递归。求以root为根并且和为sum的路径等于。
1root为空,那么为空(不存在这个路径)。
2root为叶节点,并且sum等于root.val,返回root这个单节点路径。
3以root的左子树为根并且和为sum-root.val的路径加上root(若该路径存在)。
4以root的右子树为根并且和为sum-root.val的路径加上root(若该路径存在)。
java ac代码: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>>ans = new ArrayList(100); if(root == null)return ans; if(root.left == null && root.right == null && sum == root.val) { List<Integer> t = new LinkedList(); t.add(root.val); ans.add(t); return ans; } List<List<Integer>>t1 = pathSum(root.left,sum-root.val); List<List<Integer>>t2 = pathSum(root.right,sum-root.val); if(t1.size() > 0) { for(int i = 0;i < t1.size();i++) { LinkedList<Integer>t = (LinkedList)t1.get(i); t.addFirst(root.val); ans.add(t); } } if(t2.size() > 0) { for(int i = 0;i < t2.size();i++) { LinkedList<Integer>t = (LinkedList)t2.get(i); t.addFirst(root.val); ans.add(t); } } return ans; } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
测试驱动开发的艺术
Lasse Koskela / 李贝 / 人民邮电出版社 / 20101023 / 59.00元
在传统的软件开发中,开发人员对于代码是否正确心中无底,一切依赖于后期的测试环节。极限编程反其道而行之,主张采用测试驱动开发(TDD)的方法,即通过测试定义所要开发的功能的接口,然后实现功能的开发过程。TDD通过不断地测试推动代码的开发,既简化了代码,又保证了软件质量。 本书采用“手把手”的教学方式,通过大量实例来解释TDD,还专门用几章的篇幅来讲解如何为难于测试的技术编写单元测试。全书内容循......一起来看看 《测试驱动开发的艺术》 这本书的介绍吧!