(*)剑指offer 面试题27：二叉搜索时与双向链表

题目：
输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

struct binaryTreeNode {
    int                                  m_nValue;
    binaryTreeNode*            m_pLeft;
    binaryTreeNode*            m_pRight;
};

解法：
分析：二叉搜索树的特点：左子树都比根小，右子树都比根大。对于根结点，它的上一个结点即为左子树中最大的那个结点，下一个结点即为右子树中最小的结点

void convertNode(binaryTreeNode* pRoot, binaryTreeNode** pLastNodeInList) {
    if (pRoot == 0)    return;
    binaryTreeNode  *pCurrent = pRoot;
    if (pCurrent->m_pLeft) {
        convertNode(pCurrent->m_pLeft, pLastNodeInList);
    }
    pCurrent->m_pLeft = *pLastNodeInList;
    if (*pLastNodeInList != 0) {
        (*pLastNodeInList)->m_pRight = pCurrent;
    }
    *pLastNodeInList = pCurrent;
    if (pCurrent->m_pRight) {
        convertNode(pCurrent->m_pRight, pLastNodeInList);
    }
}

binaryTreeNode*  convert(binaryTreeNode* pRoot) {
    binaryTreeNode* pLast = 0;
    convertNode(pRoot, &pLast);
    while (pLast != 0 && pLast->m_pLeft != 0) {
        pLast = pLast->m_pLeft;
    }
    return pLast;
}