面接100題:4.ある値のすべてのパスを2元ツリーで見つけ、

Julyのブログを転載して参考にするhttp://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.htmlあ、どうもありがとう!
タイトル:
整数と二元ツリーを入力します.ツリーのルートノードからリーフノードまでのすべてのノードにアクセスしてパスを形成します.入力した整数に等しいすべてのパスを印刷します.例えば、整数22と次のような二元ツリーを入力する
        10
      /   \
     5    12
  /   \
 4     7
10、12、10、5、7の2つのパスが印刷されます.
分析:
ノードにアクセスすると、そのノードをパスに追加し、現在のノードの値を加算します.現在のノードがリーフノードであり、現在のパスの和が入力した整数に等しい場合、現在のパスは要求に合致し、印刷されます.現在のノードがリーフノードでない場合は、そのサブノードにアクセスし続けます.現在のノードアクセスが終了すると、再帰関数は自動的に親ノードに戻ります.したがって、関数が終了する前に、パス上で現在のノードを削除し、現在のノードの値を減算して、親ノードに戻るときにパスがルートノードから親ノードへのパスであることを確認します.保存パスのデータ構造は、パスが再帰呼び出し状態と一致しなければならないため、再帰呼び出しの本質はスタックとスタックを出るプロセスであることがわかります.

/*Title: 4.                 
Author:  gocode
Date:    2012-10-08*/

#include <iostream>
#include <vector>
using namespace std;

//          
struct  BSTreeNode
{
    int m_nValue;
    BSTreeNode *m_pLeft;
    BSTreeNode *m_pRight;
};

//           
//     vector      、     ，   
void FindPath(BSTreeNode *pTreeNode, int expectedSum, vector<int>& path, int& currentSum)
{
    if(!pTreeNode)
        return;
    currentSum += pTreeNode->m_nValue;
    path.push_back(pTreeNode->m_nValue);
 
    //         ，            ，    
    bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);
    if(currentSum == expectedSum && isLeaf)
    {
        for(vector<int>::iterator iter = path.begin(); iter != path.end(); ++ iter)
            cout << *iter << " ";
        cout << endl;
    }

    //           ，        、   
    if(pTreeNode->m_pLeft)
        FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);
    if(pTreeNode->m_pRight)
        FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);
 
    //          ，        ，      ，   
    currentSum -= pTreeNode->m_nValue;
    path.pop_back();
}

//     
//        ，   &  ，         
void AddBSTreeNode(BSTreeNode *&pCurrent, int value)
{
    if(NULL == pCurrent)
    {
        BSTreeNode *pNewNode = new BSTreeNode();
        pNewNode->m_pLeft = NULL;
        pNewNode->m_pRight = NULL;
        pNewNode->m_nValue = value;
        pCurrent = pNewNode;
    }
    else
    {
        if(value < pCurrent->m_nValue)
            AddBSTreeNode(pCurrent->m_pLeft, value);
        else if(value > pCurrent->m_nValue)
            AddBSTreeNode(pCurrent->m_pRight, value);
        else
            cout<<"Duplicate value is not allowed."<<endl;
    }
}

void main()
{
    vector<int> resultpath;
    int resultSum = 0;
    BSTreeNode * pRoot = NULL;
 
    AddBSTreeNode(pRoot, 10);
    AddBSTreeNode(pRoot, 5);
    AddBSTreeNode(pRoot, 12);
    AddBSTreeNode(pRoot, 4);
    AddBSTreeNode(pRoot, 7);
 
    cout<<"Result is: "<<endl;
    FindPath(pRoot, 22, resultpath, resultSum);
    system("pause");
}