e******i
发帖数: 106 | 1 是树那章的。
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. Note that a path
can start or end anywhere in the tree.
书上的解法如下：
public void findSumPath(TreeNode root, int sum){
int depth = getDepth(root);
int[] path = new int[depth];
findSumPath(root, path, sum, 0);
}
public void findSumPath(TreeNode root, int[] path, int sum, int level){
if(root == null){
return null;
}
path[level] = root.val;
int temp = 0;
for(int i = level; i >=0; i--){
temp+=path[i];
if(temp==sum){
print(path, i ,level);
}
}
findSumPath(root.left, path, sum, level+1);
findSumPath(root.right, path, sum, level+1);
path[level] = Integer.MIN_VALUE;
}
我不明白的是，题目要求在一个树里找任意的path，为什么解法给人的感觉像是从root
到每一个节点的path呢？ |
A******g
发帖数: 612 | 2 每一次call到findSumPath函数的时候path里就有一条从root到现在这个node的路径
比如 node 0 -> node 5 -> node 8 -> node 9(现在的节点）
value: (10) (-5) (5) 7
比如目标sum是7
看那个for loop是从后往前加
node 9 (7) sum = 7, 符合，打印结果
node 8 -> node 9 sum =12
node 5 -> node 8 -> node9 sum = 7 符合，打印结果
...
如此类推 |
c********t
发帖数: 5706 | 3 嗯，其实题目应该是 a path can start from any ancestor node to its any
successor node.
【在 e******i 的大作中提到】
: 是树那章的。
: 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. Note that a path
: can start or end anywhere in the tree.
: 书上的解法如下：
: public void findSumPath(TreeNode root, int sum){
: int depth = getDepth(root);
: int[] path = new int[depth];
: findSumPath(root, path, sum, 0);
: }
|
e******i
发帖数: 106 | 4
对，我也是这么想的，不是任意节点间的
【在 c********t 的大作中提到】
: 嗯，其实题目应该是 a path can start from any ancestor node to its any
: successor node.
|
e******i
发帖数: 106 | 5
你说的我懂，我觉得给出的解法无法找出终点和起点在同一个level上的path
【在 A******g 的大作中提到】
: 每一次call到findSumPath函数的时候path里就有一条从root到现在这个node的路径
: 比如 node 0 -> node 5 -> node 8 -> node 9(现在的节点）
: value: (10) (-5) (5) 7
: 比如目标sum是7
: 看那个for loop是从后往前加
: node 9 (7) sum = 7, 符合，打印结果
: node 8 -> node 9 sum =12
: node 5 -> node 8 -> node9 sum = 7 符合，打印结果
: ...
: 如此类推
|
d*****n
发帖数: 23 | 6 我开始也有这个疑惑，但后来发现tree的题应该是默认不提供parent的访问的，只能从
parent访问child |
e******i
发帖数: 106 | 7
你说的对，所以是她题目说的不清楚。我觉得解法是backtrack
【在 d*****n 的大作中提到】
: 我开始也有这个疑惑，但后来发现tree的题应该是默认不提供parent的访问的，只能从
: parent访问child
|
A******g
发帖数: 612 | 8 对，career这题是这能从parent到child的path
leetcode上有一题是这个的升级版，从任意node开始，然后任何一步可以向上到parent
，也可以向下到child的
【在 e******i 的大作中提到】
:
: 你说的对，所以是她题目说的不清楚。我觉得解法是backtrack
|
