1. 题目描述
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
2. 题目分析
- 首先，我们要明白路径指的是什么
如上所示，路径有4条，分别为：
1——>2——>4 路径值：7
1——>2——>5——>7 路径值：15
1——>2——>5——>8 路径值：16
1——>3——>6 路径值：10
如果，当前的target等于上述路径的值，则输出该路径 - 我们创建需要返回的元素及一个链式的数组表
ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list = new ArrayList<Integer>();
如果当前树为空的话，则：
if (root == null) { return listAll; }
不为空的话，则将root结点添加到list中且刷新target的值：
list.add(root.val); target = target - root.val;
如果碰到target为0且左右节点都为null的位置，则将现在的list添加至listAll：
if (target == 0 && root.left == null && root.right == null) { listAll.add(new ArrayList<Integer>(list)); } 这里要注意关于new一个新的list的问题：因为路径可能有多条，所以为了不影响后续操作，我们每一次遍历建立一个新的list
对其左子树进行遍历：FindPath(root.left, target);
对其右子树进行遍历：FindPath(root.right, target);
如果到达叶节点的时候，我们需要往上返回一层，才能接着遍历：list.remove(list.size()-1);
最后返回整个listAll
3. 题目代码
import offer.Test20.TreeNode; public class Test24 { ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>(); ArrayList<Integer> list = new ArrayList<Integer>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { if (root == null) { return listAll; } list.add(root.val); target = target - root.val; if (target == 0 && root.left == null && root.right == null) { listAll.add(new ArrayList<Integer>(list)); } FindPath(root.left, target); FindPath(root.right, target); list.remove(list.size()-1); return listAll; } }
