113. Path Sum II - Medium
发布时间:2020-12-14 05:17:57 所属栏目:大数据 来源:网络整理
导读:Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum. Note:?A leaf is a node with no children. Example: Given the below binary tree and? sum = 22 , 5 / 4 8 / / 11 13 4 / / 7 2 5 1 Return:
Given a binary tree and a sum,find all root-to-leaf paths where each path‘s sum equals the given sum. Note:?A leaf is a node with no children. Example: Given the below binary tree and? 5 / 4 8 / / 11 13 4 / / 7 2 5 1 Return: [ [5,4,11,2],[5,8,5] ] ? time: O(n),space: O(height) /** * 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>> res = new ArrayList<>(); List<Integer> list = new ArrayList<>(); pathSum(root,sum,list,res); return res; } public void pathSum(TreeNode root,int sum,List<Integer> list,List<List<Integer>> res) { if(root == null) { return; } if(root.left == null && root.right == null) { if(sum == root.val) { list.add(root.val); res.add(new ArrayList<>(list)); list.remove(list.size() - 1); } return; } list.add(root.val); pathSum(root.left,sum - root.val,res); pathSum(root.right,res); list.remove(list.size() - 1); } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |