##题目描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
##解题思路
1，从根节点开始，分别向左右递归寻找
2，如果当前路径值刚好相等并且刚好到达叶子节点，则把路径添加到list里
3，如果当前路径值小于目标值，就向左子树或者右子树进发
4，如果当前路径值和大于目标值或者已经找到一条路径则回到上一层
##代码
/** * */ package offerTest; import java.util.ArrayList; /** * <p> * Title:FindPaths * </p> * <p> * Description: * </p> * * @author 田茂林 * @data 2017年8月20日 下午9:56:48 */ public class FindPaths { ArrayList<ArrayList<Integer>> listall = new ArrayList<ArrayList<Integer>>(); //发现路径函数 public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { ArrayList<Integer> list = new ArrayList<Integer>(); if (root == null) { return listall; } int cursum = 0; return FindPath(root, target, list, cursum); } //递归调用，存储有效路径 public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target, ArrayList<Integer> list, int cursum) { cursum += root.val; list.add(root.val); // 如果刚好相等，将该路径添加到路径集里 if (cursum == target && root.left == null && root.right == null) { ArrayList<Integer> path = new ArrayList<Integer>(); for (int i = 0; i < list.size(); i++) { path.add(list.get(i)); } listall.add(path); } // 如果小于当前值，且左子树不为空，则向左子树进发 if (cursum < target && root.left != null) { FindPath(root.left, target, list, cursum); } // 如果小于当前值，且右子树不为空，则向右子树进发 if (cursum < target && root.right != null) { FindPath(root.right, target, list, cursum); } //如果当前路径值和大于目标值或者已经找到一条路径则回到上一层 cursum -= root.val; list.remove(list.size() - 1); return listall; } public static void main(String[] args) { // TODO Auto-generated method stub } }
