Amazon : construct double linklist out of a BST

construct double linklist out of a BST

如题

咋说呢，这题算是相当简单了，普通的递归：

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

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

void _inner_chg_tree(NODE* pRoot, NODE*& pLft, NODE*& pRgt);
NODE* TurnToDBLnk(NODE* pRoot)
{
        if (NULL == pRoot) return NULL;

        NODE* pHead = NULL;
        NODE* pTail = NULL;
        _inner_chg_tree(pRoot, pHead, pTail);

        return pHead;
}

void _inner_chg_tree(NODE* pRoot, NODE*& pLft, NODE*& pRgt)
{
        assert(NULL != pRoot);

        pLft = pRgt = pRoot;
        if (NULL != pRoot->pLft)
        {
                NODE* pTmpL, *pTmpR;
                _inner_chg_tree(pRoot->pLft, pTmpL, pTmpR);
                pLft = pTmpL;
                pRoot->pLft = pTmpR;
                pTmpR->pRgt = pRoot;
        }

        if (NULL != pRoot->pRgt)
        {
                NODE* pTmpL, *pTmpR;
                _inner_chg_tree(pRoot->pRgt, pTmpL, pTmpR);
                pRgt = pTmpR;
                pRoot->pRgt = pTmpL;
                pTmpL->pLft = pRoot;
        }
}