path-sum
(1过)
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example:
Given the below binary tree andsum = 22,
5 / 4 8 / / 11 13 4 / 7 2 1
return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5 / 4 8 / / 11 13 4 / 7 2 1
返回 true
, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2
。
public class PathSum { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null && root.val == sum) { return true; } else { return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val); } } }
path-sum-ii
(1过)
给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树,以及目标和 sum = 22
,
5 / 4 8 / / 11 13 4 / / 7 2 5 1
返回:
[ [5,4,11,2], [5,8,4,5] ]
解答:自己写的,和答案差不多,很久之前剑指offer好像做过
public class Solution { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) { ArrayList<Integer> list = new ArrayList<>(); path(root,sum,list); return result; } void path(TreeNode root, int sum,ArrayList<Integer> list) { if (root == null) { return ; } if (root.left == null && root.right == null && root.val == sum) { list.add(root.val); result.add(new ArrayList<>(list)); //new ArrayList<>(list) list.remove(list.size()-1); return ; } else { list.add(root.val); path(root.left,sum-root.val,list); path(root.right,sum-root.val,list); list.remove(list.size()-1); return; } } }