NLF(无限光年) question
Q
Count the number of paths where the sum of the values of the nodes on the path is equal to a given value k
Binary Tree Search
import java.util.Stack;
public class TreeMain {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(2);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(3);
int k = 6;
int result = printFromRootToLeaves(root, k);
System.err.println("Number of paths with sum " + k + ": " + result);
}
public static int printFromRootToLeaves(TreeNode node, int k) {
return printFromRootToLeavesHelper(node, k, new Stack<>(), 0);
}
private static int printFromRootToLeavesHelper(TreeNode node, int k, Stack<Integer> path, int sum) {
if (node == null) {
return 0;
}
path.push(node.val);
sum += node.val;
int count = 0;
if (node.left == null && node.right == null && sum == k) {
printPath(path);
count = 1;
}
count += printFromRootToLeavesHelper(node.left, k, path, sum);
count += printFromRootToLeavesHelper(node.right, k, path, sum);
path.pop();
return count;
}
private static void printPath(Stack<Integer> path) {
for (int val : path) {
System.out.print(val + " ");
}
System.out.println();
}
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}