题目描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
private int sum = 0;
private ArrayList<ArrayList<Integer>> array = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> a = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
find(root, target);
return array;
}
private void find(TreeNode root, int target) {
if(root == null)
return;
sum += root.val;
if(sum < target) {
a.add(root.val);
find(root.left, target);
find(root.right, target);
a.remove(a.size() - 1);
sum -= root.val;
}else {
if(sum > target) {
sum -= root.val;
return;
}else {
if(root.left == null && root.right == null) {
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int i : a){
temp.add(i);
}
temp.add(root.val);
array.add(temp);
}
sum -= root.val;
return;
}
}
}
public static void main(String[] args) {
Solution obj = new Solution();
int[] arr = {10,5,12,4,7};
TreeNode root = build(arr);
obj.FindPath(root, 22);
}
private static TreeNode build(int[] arr){
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(arr == null || arr.length == 0) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
int i = 0;
int length = arr.length;
queue.add(root);
while(!queue.isEmpty()) {
TreeNode temp = queue.poll();
i++;
if(i <length) {
TreeNode left = new TreeNode(arr[i]);
temp.left = left;
queue.add(left);
}else{
temp.left = null;
}
i++;
if(i < length) {
TreeNode right = new TreeNode(arr[i]);
temp.right = right;
queue.add(right);
}else {
temp.right = null;
}
}
return root;
}
}
