find all pairs of elements in a balanced BST that sum to a certain number

Given a  number. find all pairs of elements in a balanced bst,
which sum to this number. Make sure you don't return same pair again

如果找的数是8,有很多个4... Hoho...

咋说呢，这题如果数都是不重复的，因为是平衡树，直接查找就可以了，但是如果有重复的数，靠，还不如干脆拿个数组装下来得了....

假设数不重复：

struct NODE
{
        int nVal;
        NODE* pLft;
        NODE* pRgt;

        NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};

NODE* GetPair(int nSum, NODE* pRoot, NODE* pCur)
{
        assert(pRoot != NULL && pCur != NULL);
        if (nSum - pCur->nVal <= pCur->nVal) return NULL;

        NODE* pRes = pRoot;
        while (NULL != pRes)
        {
                if (pRes->nVal == nSum - pCur->nVal)
                        break;
                if (pRes->nVal < nSum - pCur->nVal)
                        pRes = pRes->pRgt;
                else
                        pRes = pRes->pLft;
        }

        return pRes;
}

void GetPairsToSum(int nSum, NODE* pRoot, NODE* pCur, vector<pair<NODE*, NODE*>>& vec)
{
        if (NULL == pCur || NULL == pRoot) return;

        GetPairsToSum(nSum, pRoot, pCur->pLft, vec);

        NODE* pRes = GetPair(nSum, pRoot, pCur);
        if (NULL != pRes)
                vec.push_back(make_pair(pCur, pRes));

        GetPairsToSum(nSum, pRoot, pCur->pRgt, vec);
}