丝丝说,她在发包子前问一下# Joke - 肚皮舞运动
S*C
1 楼
4.9 You are given a binary tree in which each node contains a value. Design
an algorithm to print all paths which sum to a given value. The path does
not need to start or end at the root or a leaf
Page 237
他的答案如下
package Question4_9;
import CtCILibrary.TreeNode;
public class Question {
public static void findSum(TreeNode node, int sum, int[] path, int level
) {
if (node == null) {
return;
}
/* Insert current node into path */
path[level] = node.data;
int t = 0;
for (int i = level; i >= 0; i--){
t += path[i];
if (t == sum) {
print(path, i, level);
}
}
findSum(node.left, sum, path, level + 1);
findSum(node.right, sum, path, level + 1);
/* Remove current node from path. Not strictly necessary, since we
would
* ignore this value, but it's good practice.
*/
path[level] = Integer.MIN_VALUE;
}
public static int depth(TreeNode node) {
if (node == null) {
return 0;
} else {
return 1 + Math.max(depth(node.left), depth(node.right));
}
}
public static void findSum(TreeNode node, int sum) {
int depth = depth(node);
int[] path = new int[depth];
findSum(node, sum, path, 0);
}
private static void print(int[] path, int start, int end) {
for (int i = start; i <= end; i++) {
System.out.print(path[i] + " ");
}
System.out.println();
}
public static void main(String [] args){
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(1);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(8);
root.right.left = new TreeNode(2);
root.right.right = new TreeNode(6);
findSum(root, 8);
}
}
这种解法错在只能求单边的单线段path，不能求倒勾形状的path，而倒钩型path显然是
不能忽略的。
比如下面的例子中如果sum等于9显然是存在path的： 3-5-1
但这种解法根本把他忽略了。Career cup出到第5版了还犯这种幼稚的错误真是让人无
语。
5
3 1
4 8 2 6
这题谁有正确的解法？
an algorithm to print all paths which sum to a given value. The path does
not need to start or end at the root or a leaf
Page 237
他的答案如下
package Question4_9;
import CtCILibrary.TreeNode;
public class Question {
public static void findSum(TreeNode node, int sum, int[] path, int level
) {
if (node == null) {
return;
}
/* Insert current node into path */
path[level] = node.data;
int t = 0;
for (int i = level; i >= 0; i--){
t += path[i];
if (t == sum) {
print(path, i, level);
}
}
findSum(node.left, sum, path, level + 1);
findSum(node.right, sum, path, level + 1);
/* Remove current node from path. Not strictly necessary, since we
would
* ignore this value, but it's good practice.
*/
path[level] = Integer.MIN_VALUE;
}
public static int depth(TreeNode node) {
if (node == null) {
return 0;
} else {
return 1 + Math.max(depth(node.left), depth(node.right));
}
}
public static void findSum(TreeNode node, int sum) {
int depth = depth(node);
int[] path = new int[depth];
findSum(node, sum, path, 0);
}
private static void print(int[] path, int start, int end) {
for (int i = start; i <= end; i++) {
System.out.print(path[i] + " ");
}
System.out.println();
}
public static void main(String [] args){
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(1);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(8);
root.right.left = new TreeNode(2);
root.right.right = new TreeNode(6);
findSum(root, 8);
}
}
这种解法错在只能求单边的单线段path，不能求倒勾形状的path，而倒钩型path显然是
不能忽略的。
比如下面的例子中如果sum等于9显然是存在path的： 3-5-1
但这种解法根本把他忽略了。Career cup出到第5版了还犯这种幼稚的错误真是让人无
语。
5
3 1
4 8 2 6
这题谁有正确的解法？
