题目描述
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 下图的二叉树有两条和为 22 的路径：10, 5, 7 和 10, 12 题目链接：牛客网
解题思路
import java
.util
.*
;
public class Main {
public static class TreeNode {
int val
= 0;
TreeNode left
= null
;
TreeNode right
= null
;
public TreeNode(int val
) {
this.val
= val
;
}
}
public static ArrayList
<ArrayList
<Integer>> list
= new ArrayList();
public static void main(String
[] args
) {
TreeNode root
= new TreeNode(10);
root
.right
= new TreeNode(12);
root
.left
= new TreeNode(5);
root
.left
.left
= new TreeNode(4);
root
.left
.right
= new TreeNode(7);
ArrayList
<ArrayList
<Integer>> infos
= findPath(root
,22);
for (ArrayList
<Integer> info
: infos
) {
printList(info
);
}
}
public static ArrayList
<ArrayList
<Integer>> findPath(TreeNode root
,int target
) {
backtracking(root
,target
,new ArrayList<>());
return list
;
}
public static void backtracking(TreeNode node
,int target
,ArrayList
<Integer> path
) {
if (node
== null
) {
return;
}
path
.add(node
.val
);
target
-= node
.val
;
if (target
== 0 && node
.left
== null
&& node
.right
== null
) {
list
.add(new ArrayList<>(path
));
}else {
backtracking(node
.left
,target
,path
);
backtracking(node
.right
,target
,path
);
}
path
.remove(path
.size() - 1);
}
public static void printList(ArrayList list
) {
for (int i
= 0;i
< list
.size();i
++) {
System
.out
.print(list
.get(i
) + " ");
}
System
.out
.println();
}
}
测试结果
