## *【九度OJ1368】|【剑指offer25】二叉树中和为某一值的路径 原

aqia358

``````5 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1
1 5
1 -1 -1``````

``````result:
A path is found: 1 2 5
A path is found: 1 3
result:``````

``````import java.io.BufferedReader;
import java.io.IOException;
import java.io.StreamTokenizer;
import java.util.Stack;

public class Main {
public static int target;

static class Node{
public int id;
public int data;
public Node left;
public Node right;
public Node(int id){
this.id = id;
}
}
public static Node find(int id, Node node){
if(node != null){
if(node.id == id)
return node;
Node l = find(id, node.left);
Node r = find(id, node.right);
if(l != null){
return l;
}else if(r != null){
return r;
}else
return null;
}else{
return null;
}
}
public static void search(Node node, Stack<Integer> stack, int sum){
if(node == null || node.id == -1){
return;
}else{
sum += node.data;
stack.push(node.id);
search(node.left, stack, sum);
search(node.right, stack, sum);
if(sum == target && node.left.id == -1 && node.right.id == -1){
System.out.print("A path is found:");
for(int i:stack){
System.out.print(" "+i);
}
System.out.println();
}
stack.pop();
}
}

public static void main(String[] args) throws IOException {

while(st.nextToken() != StreamTokenizer.TT_EOF){
int n = (int)st.nval;
st.nextToken();
Main.target = (int)st.nval;
Node root = new Node(1);
for(int i = 1; i <= n; i++){
Node node = Main.find(i, root);
st.nextToken();
node.data = (int)st.nval;
st.nextToken();
int l = (int)st.nval;
st.nextToken();
int r = (int)st.nval;
if(l > r){
node.left = new Node(r);
node.right = new Node(l);
}else{
node.left = new Node(l);
node.right = new Node(r);
}
}
System.out.println("result:");
Main.search(root, new Stack<Integer>(), 0);
}
}

}``````

### aqia358

[算法总结] 20 道题搞定 BAT 面试——二叉树

09/04
0
0
python剑指offer66题

lyy0905
06/03
0
0
[剑指offer] 二叉树中和为某一值的路径

07/01
0
0

dby_freedom
11/05
0
0

2017/11/08
0
0

import com.alibaba.fastjson.JSON;import java.beans.PropertyDescriptor;import java.lang.annotation.*;import java.lang.reflect.Field;import java.lang.reflect.Method;impo......

laolin23
36分钟前
2
0
WordPress没有上级目录的写权限

sudo chmod -R 777 wordpress/wp-content

43分钟前
5
0

44分钟前
6
0
ASP.NET Core MVC 静态文件配置

whltian

2
0
linux之自定义命令

8
0