输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
二叉树中和为某一值的路径
http://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca
版权声明：本文为CSDN博主「AnApplePie」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u014525494/article/details/80978647
原文链接：https://blog.csdn.net/u014525494/article/details/80978647
思路分析：首先思考节点值的和为输入的整数，每条路径都一定是从根节点到叶子节点，在数据结构中从根节点到叶子节点的遍历称之为深度优先遍历DFS。因此整个过程可以采用先序遍历方式的DFS，即根节点》左子树》右子树。随后考虑一次遍历完成后的处理，当一次遍历完成后，如果输入整数值恰好等于节点值之和，则输出这条路径并且回退一个节点；如果不等于则直接回退一个节点，即回退到当前节点的父节点，如果该父节点有右孩子，则继续遍历，否则继续回退。考虑回退到根节点，此时如果它有右孩子，则继续遍历，否则整个DFS结束。
数据结构分析：使用java完成整个题目，采用ArrayList<ArrayList<Integer>>，举个如下的例子，输入整数为22。
第一次遍历 10,5,4 19<22，因此ArrayList要使用remove函数回退到父节点5上，开始寻找右孩子。
第二次遍历 10,5,7 22=22，此时正好输出这条路径（将路径添加到ArrayList中），10,5,7，回退到父节点5上，此时5的左右孩子都已遍历完成，因此回退到父节点10
第三次遍历 10,12 22=22，此时正好输出这条路径（将路径添加到ArrayList中），10,12，由于12没有左右孩子，因此直接回退到父节点10
由于根节点10左右孩子都已遍历完成，因此整个DFS结束。
需要注意的是不论路径的值是否等于输入整数值，都要回退，即使用remove函数移除路径上的最后一个节点。
————————————————
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> path = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null){
return result;//改
}
path.add(root.val);
if(root.val == target && root.left == null && root.right == null){
result.add(new ArrayList<>(path));
}
if(root.left != null && root.val <= target){
FindPath(root.left, target - root.val);
}
if(root.right != null && root.val <= target){
FindPath(root.right, target - root.val);
}
path.remove(path.size()-1);
return result;
}
} 
查看18道真题和解析