C++二叉搜索樹與雙向鏈表（劍指Offer精簡版）

題目：輸入一棵二叉搜索樹，將該二叉搜素樹轉換成一個排序的雙向鏈表。
二叉樹節點定義如下：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

解題思路：
由于通過中序排序可以轉化為雙向鏈表，因此，通過中序遍歷的方法（左根右）的遞歸方法可以解決問題，解決完之后，pList節點指向雙向鏈表的尾結點，pList節點需要通過遍歷，返回到頭節點，同樣，我們也可以通過逆向中序遍歷的方法之間完成，代碼如下：

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* pList=nullptr;//雙向鏈表的頭節點
        Convert(pRootOfTree,pList);
        return pList;
    }
    void Convert(TreeNode* pRootOfTree,TreeNode*& pList)
    {
        if(pRootOfTree==nullptr)//遞歸的出口
            return;
        if(pRootOfTree->right!=nullptr)//遞歸處理右子樹
            Convert(pRootOfTree->right,pList);
        pRootOfTree->right=pList;//right相當于pNext
        if (pList != nullptr)
            pList->left = pRootOfTree;//left相當于pPre
        pList = pRootOfTree;//pList節點從尾結點依次移動到頭節點
        if (pRootOfTree->left != nullptr)//遞歸處理左子樹
            Convert(pRootOfTree->left, pList);
    }
};