1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

///////////////////////////////////////////////////////////////////////
// Find paths whose sum equal to expected sum
///////////////////////////////////////////////////////////////////////
void FindPath
(
    BinaryTreeNode   *pTreeNode,    // a node of binary tree
    int               expectedSum,  // the expected sum
    std::vector<int> &path,         // a path from root to current node
    int              &currentSum    // the sum of path
)
{
    if(!pTreeNode)
        return;

currentSum += pTreeNode->m_nValue;
    path.push_back(pTreeNode->m_nValue);

// if the node is a leaf, and the sum is same as pre-defined,
    // the path is what we want. print the path
    bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
    if(currentSum == expectedSum && isLeaf)
    {
        std::vector<int>::iterator iter = path.begin();
        for(; iter != path.end(); ++ iter)
            std::cout << *iter << '\t';
        std::cout << std::endl;
    }

// if the node is not a leaf, goto its children
    if(pTreeNode->m_pLeft)
        FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
    if(pTreeNode->m_pRight)
        FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

// when we finish visiting a node and return to its parent node,
    // we should delete this node from the path and
    // minus the node's value from the current sum
    currentSum -= pTreeNode->m_nValue;
    path.pop_back();
}

void FindPath(
    BinaryTreeNode   *pTreeNode,    // a node of binary tree
    int               expectedSum  // the expected sum
)
{
    ;
    std::vector<int> path;
    FindPath(pTreeNode, expectedSum, path, curSum);
}