Amazon : 二叉树中寻找节点值的和等于指定数字的路径个数

You are given a binary tree in which each node contains a value Design an algorithm
to find the number of all paths which sum up to that value

PS. Path 这里不知道具体代表什么，应该是任意两个不同节点间的所有可能的path, 不一定是最短，包括由上而下的simple path和带拐弯的path,遍历了重复节点的path都算。

背包问题的拓展
从儿子到父亲顺序DP
F=sum{F[j][s-w]} j is son of i  and  for S>=s>w
F[w]=1
这可以把所有不跨过root的搞定
跨过root的单独处理下，这里是二叉树，直接sum{F[son1][s1]*F[son2][S-s1-w[root]]}就行了
可以很容易拓展的多叉树
cldndx 发表于 2011-6-19 17:53

O(nlogn)的时间复杂度，O(n)的空间应该可以解
不算NPC问题吧

cldndx 发表于 2011-6-24 23:59
对哦，我想复杂了，直接穷举就n^2了，如果权是正数可以用单调性优化下

直接穷举然后用lca转rmq貌似直接可以做到O(n^2)？而不是O(n^3)。。。目测的。