100题_04 在二元树中找出和为某一值的所有路径

   / \

  5  12

 / \

4  7
则打印出两条路径：10, 12和10, 5, 7。

想想其实把所有的路径找出来，然后求和去算就可以解决。但是针对这题，有些路径可以在完全找出来之前就否定了……所以需要剪枝。

利用递归的思想：对于结点10，我们只要在其左右两个子树中找出路径为12的就可了，所以很快就可以得到结果，注意，我们需要记录路径。

下面是代码：

View Code void BinaryTree::FindPath(BinaryTreeNode *root, int va, vector<int> &path)
{
    if (root == NULL)
        return;
    path.push_back(root->m_nValue);
    int value = va - root->m_nValue;
    if (value == 0)
    {
        if (root->m_pLeft == NULL || root->m_pRight == 0)
        {
            for (vector<int>::iterator it = path.begin(); it != path.end(); it++)
                cout<<*it<<' ';
            cout<<endl;
        }
        path.pop_back();
        return;
    }

    if (value < 0)
        return;
    if (root->m_pLeft)
        FindPath(root->m_pLeft, value, path);
    if (root->m_pRight)
        FindPath(root->m_pRight, value, path);
    path.pop_back();
}