/********************************************************************
    
    purpose:    在二元樹中找出和為某一值的所有路徑
    
    題目：輸入一個整數和一棵二元樹。
    從樹的根結點開始往下訪問一直到葉結點所經過的所有結點形成一條路徑。
    打印出和與輸入整數相等的所有路徑。
    例如 輸入整數22和如下二元樹
       10  
       / \   
      5  12   
     / \   
    4   7
    則打印出兩條路徑：10, 12和10, 5, 7。

    二元樹節點的數據結構定義為：
    struct BinaryTreeNode // a node in the binary tree
    {
    int m_nValue; // value of node
    BinaryTreeNode *m_pLeft; // left child of node
    BinaryTreeNode *m_pRight; // right child of node
    };

*********************************************************************/
#include <iostream>
#include <vector>

using namespace std;

struct BinaryTreeNode // a node in the binary tree
{
    int m_nValue; // value of node
    BinaryTreeNode *m_pLeft; // left child of node
    BinaryTreeNode *m_pRight; // right child of node
};

void PathEqualN(vector<BinaryTreeNode*> vect, BinaryTreeNode* pNode, int sum, int destSum)
{

    sum += pNode->m_nValue;
    if (pNode->m_pLeft == NULL && pNode->m_pRight == NULL) {
        if (sum == destSum) {
            for (int i = 0; i < vect.size(); i++) {
                cout<<vect[i]->m_nValue<<" ";
            }
            cout<<pNode->m_nValue<<endl;
        }
        return;
    }

    vect.push_back(pNode);
    if (pNode->m_pLeft != NULL) {
        PathEqualN(vect, pNode->m_pLeft, sum, destSum);
    } 
    if (pNode->m_pRight != NULL) {
        PathEqualN(vect, pNode->m_pRight, sum, destSum);
    }
    vect.pop_back();
}

void Test_PathEqualN()
{
    // init tree
    BinaryTreeNode node4; node4.m_nValue = 4; node4.m_pLeft = NULL; node4.m_pRight = NULL;
    BinaryTreeNode node7; node7.m_nValue = 7; node7.m_pLeft = NULL; node7.m_pRight = NULL;
    BinaryTreeNode node5; node5.m_nValue = 5; node5.m_pLeft = &node4; node5.m_pRight = &node7;

    BinaryTreeNode node12; node12.m_nValue = 12; node12.m_pLeft = NULL; node12.m_pRight = NULL;

    BinaryTreeNode root; root.m_nValue = 10; root.m_pLeft = &node5; root.m_pRight = &node12;

    // search
    vector<BinaryTreeNode*> vect;
    PathEqualN(vect, &root, 0, 22);


}

貌似都不是太難，難道是要考慮細節？？