共计 1097 个字符,预计需要花费 3 分钟才能阅读完成。
题目地址: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;
}
}