leetcode113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example: Given the below binary tree and  sum = 22 , 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1

return

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

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> list=new ArrayList<List<Integer>>(); List<Integer> li=new ArrayList<Integer>(); if(root==null) return list; int currentSum=0; find(root,sum,currentSum,li,list); return list; } public static void find(TreeNode root,int sum,int currentSum,List<Integer> li,List<List<Integer>> list){ currentSum+=root.val; li.add(root.val); boolean isLeaf=root.left==null&&root.right==null; if(currentSum==sum&&isLeaf){ List<Integer> ls=new ArrayList<Integer>(li); list.add(ls); } if(root.left!=null) find(root.left,sum,currentSum,li,list); if(root.right!=null) find(root.right,sum,currentSum,li,list); li.remove(li.size()-1); } } 思路：用前序遍历的方式访问某一个节点时，吧该节点添加到路径上，并累加该节点的值，如果该节点为叶子节点并且路径中节点的值刚好等于

输入的整数，当前的路径符合要求。如果当前不是叶子节点，则继续访问它的叶子节点。当前节点访问结束后，递归函数将自动回到它的父节点。因此我们在函数退出之前要在路径上删除当前节点并减去当前节点的值，刚好是从根节点到父节点的路径。