Groupon面经：Find paths in a binary tree summing to a target value - neverlandly - 博客园
http://stackoverflow.com/questions/4591763/find-paths-in-a-binary-search-tree-summing-to-a-target-value
Traverse through the tree from the root and do a post-order gathering of all path sums. Use a hashtable at each node to store the possible paths rooted at a node and going down-only. Key is the path sum, value is the actual path. We can construct all paths going through a node from itself and its childrens' paths.
Here is psuedo-code that implements the above, but stores only the sums and not the actual paths. For the paths themselves, you need to store the end node in the hashtable (we know where it starts, and there's only one path between two nodes in a tree).
Read full article from Groupon面经：Find paths in a binary tree summing to a target value - neverlandly - 博客园
You are given a binary tree (not necessarily BST) in which each node contains a value.
Design an algorithm to print all paths which sum up to that value. Note that
it can be any path in the tree - it does not have to start at the root.
Traverse through the tree from the root and do a post-order gathering of all path sums. Use a hashtable at each node to store the possible paths rooted at a node and going down-only. Key is the path sum, value is the actual path. We can construct all paths going through a node from itself and its childrens' paths.
Here is psuedo-code that implements the above, but stores only the sums and not the actual paths. For the paths themselves, you need to store the end node in the hashtable (we know where it starts, and there's only one path between two nodes in a tree).
function findsum(tree, target)
# Traverse the children
if tree->left
findsum(tree.left, target)
if tree->right
findsum(tree.right, target)
# Single node forms a valid path
tree.sums = {tree.value}
# Add this node to sums of children
if tree.left
for left_sum in tree.left.sums
tree.sums.add(left_sum + tree.value)
if tree.right
for right_sum in tree.right.sums
tree.sums.add(right_sum + tree.value)
# Have we formed the sum?
if target in tree.sums
we have a path
# Can we form the sum going through this node and both children?
if tree.left and tree.right
for left_sum in tree.left.sums
if target - left_sum in tree.right.sums
we have a path
# We no longer need children sums, free their memory
if tree.left
delete tree.left.sums
if tree.right
delete tree.right.sums
