*【九度OJ1368】|【剑指offer25】二叉树中和为某一值的路径
*【九度OJ1368】|【剑指offer25】二叉树中和为某一值的路径
aqia358 发表于4年前
*【九度OJ1368】|【剑指offer25】二叉树中和为某一值的路径
• 发表于 4年前
• 阅读 120
• 收藏 0
• 评论 0

``````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);
}
}

}``````

×