题目：
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
思路分析：
是图形相关的算法。首先考虑解决图形相关的广度搜索优先算法就是深度搜索优先算法。这里而言是后者。
后来回顾(重要)：
实现时，我们debug发现上面的分析过程右很大的一个漏洞。上面只做了一次判断，然而要删除一个结点元素值，实际中需要以右结点为null判断。
另外，删除5并同时删除2的实现，需要解压栈操作实现。添加到判断并删除很很难实现。
代码实现：
二叉树：
package com.stuk;public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
实现代码：
package com.stuk;import java.util.ArrayList;public class Main1 {private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();public static void main(String[] args) {TreeNode tree = new TreeNode(10);tree.left = new TreeNode(5);tree.right = new TreeNode(12);tree.left.left = new TreeNode(4);tree.left.right = new TreeNode(7);System.out.println(FindPath(tree, 22));}public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {if (root == null) {return result;}// 这是回溯法的关键，list 暂存对象。ArrayList<Integer> list = new ArrayList<>();// 回溯法backTracIng(root, target, list);return result;}private static void backTracIng(TreeNode node, int target, ArrayList<Integer> list) {if (node == null) {// 删除走到null不满足的上一个结点, 不能放这里会多移除掉元素// list.remove(list.size() - 1);// 走到结尾都不满足，结束递归return;}list.add(node.val);// 判断条件满足target -= node.val;if (target == 0 && node.left == null && node.right == null) {result.add(new ArrayList<>(list));} else {// 当前结点左孩子处理backTracIng(node.left, target, list);//list.remove(list.size() - 1); 致命分析错误，会导致多删除一个元素// 当前结点右孩子处理backTracIng(node.right, target, list);// 当右孩子为null，恢复target值// 并移除list中存储的结点值 ---- 不能做到向上多个删除比如10，5，4，要删除5和4// target += list.get(list.size() - 1);// list.remove(list.size() - 1);}// 最后解压栈向上删除最后一个元素list.remove(list.size() - 1);}}
如果觉得《二叉树深度优先搜索算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
