在二叉树中找出和为某一值的所有路径-java实现
16lz
2021-01-22
一个小算法，分享一下思路：
描述：
写一个程序创建一棵二叉树，并按照一定规则，输出二叉树根节点到叶子节点的路径。
规则如下：
1、从最顶端的根结点，到最下面的叶子节点，计算路径通过的所有节点的和，如果与设置的某一值的相同，那么输出这条路径上的所有节点。
2、从根节点遍历树时，请请按照左到右遍历，即优先访问左子树的节点。
二叉树创建规则：从上到下一层一层的，按照从左到右的顺序进行构造
输入"10,5,12,4,7"值，构造的树如下：
1）10
2）10
/
5
3）10
/\
512
4）10
/\
512
/
4
5）10
/\
512
/\
47
针对上面的二叉树，如果当前我们设置的“路径和”为19，那么输出结果为:
10,5,4
如果有多个路径，按到左到右的顺序遍历生成的结果每行显示一个显示。例如如果当前我们设置的“路径和”为22，那么输出结果为:
10,5,7
10,12
如果没有找到路径和为设置的值的路径，输出error。
输入：
输入整数N---路径和
一行字符串，多个正整数，之间用","隔开
输出：
满足条件的二叉树路径
样例输入：
22
10,5,12,4,7
样例输出：
10,5,7
10,12
实现代码：
/*
*Created on 2016年8月17日
*Copyright 2016 Yong Cai Limited crop. All Rights Reserved
*
*728**0@qq.com
*/
import java.util.Scanner;
public class Main {
public static int counter = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = Integer.valueOf(sc.nextLine());
String line = sc.nextLine();
compute(N, line);
}
public static void compute(int N, String line){
String[] arr = line.split(",");
int len = arr.length;
//从index=1开始存数据
Node[] nodeArr = new Node[len + 1];
for(int i = 0; i < len; i++){
int val = Integer.valueOf(arr[i]);
nodeArr[i + 1] = new Node(val);
}
//构建二叉树
Node root = nodeArr[1];
for(int i = 1; i < len + 1; i++){
if(i * 2 < len + 1){
nodeArr[i].left = nodeArr[2 * i];
}
if(i * 2 + 1 < len + 1){
nodeArr[i].right = nodeArr[2 * i + 1];
}
}
//printTree(root);
printPaths(root, len, N);
}
public static void printTree(Node root){
if(root == null){
return;
}
System.out.println(root.val);
if(root.left != null){
printTree(root.left);
}
if(root.right != null){
printTree(root.right);
}
}
public static void printPaths(Node root, int n, int N) {
int[] path = new int[n];
printPaths(root, path, 0, N);
if(counter == 0){
System.out.println("error");
}
}
public static void printPaths(Node root, int[] path, int pathLen, int N) {
if (root == null) return;
path[pathLen++] = root.val;
if (root.left == null && root.right == null) {
printArray(path, pathLen, N);
}
else {
printPaths(root.left, path, pathLen, N);
printPaths(root.right, path, pathLen, N);
}
}
public static void printArray(int[] ints, int len, int N) {
int total = 0;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append(ints[i] + ",");
total += ints[i];
}
if(total == N){
System.out.println(sb.toString().substring(0, sb.toString().length() - 1));
counter++;
}
}
}
class Node{
public int val;
public Node left;
public Node right;
public Node(int val){
this.val = val;
}
}