S*******C
发帖数: 822 | 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
这题谁有正确的解法？ | s******y
发帖数: 936 | 2 她的解法对她的题没有错， 你理解成了leetcode 那道题了http://oj.leetcode.com/problems/binary-tree-maximum-path-sum/. 我觉得作者对path的理解是自上向下，不能自下向上。我做leetcode 的时候也是cc150 作者那么理解的。 比如1->2->3 这是个linkedlist path 是1， 2， 3 ， 按你的理解是3,2,1 也算path，明显3不能走到2 ，这就是cc150的理解，我觉得。 | S*******C
发帖数: 822 | 3 那应该明说 print all downward paths ...
否则这答案肯定不对
【在 s******y 的大作中提到】
: 她的解法对她的题没有错， 你理解成了leetcode 那道题了http://oj.leetcode.com/problems/binary-tree-maximum-path-sum/. 我觉得作者对path的理解是自上向下，不能自下向上。我做leetcode 的时候也是cc150 作者那么理解的。 比如1->2->3 这是个linkedlist path 是1， 2， 3 ， 按你的理解是3,2,1 也算path，明显3不能走到2 ，这就是cc150的理解，我觉得。
|
|
