You are given a binary tree 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.
#include <list>
#include <iostream>
using namespace std;
struct TreeNode
{
int value;
TreeNode * left;
TreeNode * right;
TreeNode(int v)
{
value = v;
left = NULL;
right = NULL;
}
TreeNode(int v, TreeNode * l, TreeNode * r)
{
value = v;
left = l;
right = r;
}
};
void mprint(list<int> path, int length);
void findSum(TreeNode * node, int sum_value, list<int> path, int length)
{
if (node == NULL)
return;
path.push_front(node->value);
int tmp = sum_value;
list<int>::iterator iter;
int i = 0;
for (iter = path.begin(); iter != path.end(); ++iter)
{
tmp -= *iter;
if (tmp == 0)
mprint(path, i);
i ++;
}
list<int> c1(path);
list<int> c2(path);
findSum(node->left, sum_value, c1, length + 1);
findSum(node->right, sum_value, c2, length + 1);
}
void mprint(list<int> path, int length)
{
list<int>::iterator iter;
for(iter = path.begin(); length >= 0; length --)
{
cout<<*iter<<" ";
iter ++;
}
cout<<endl;
}
int main()
{
TreeNode * node0 = new TreeNode(2);
TreeNode * node1 = new TreeNode(3, node0, NULL);
TreeNode * node2 = new TreeNode(-4, node1, NULL);
TreeNode * node3 = new TreeNode(3, node2, NULL);
TreeNode * node4 = new TreeNode(1, node3, NULL);
TreeNode * node5 = new TreeNode(2, node4, NULL);
list<int> path;
findSum(node5, 5, path, 0);
return 0;
}