題目：輸入一棵二叉搜索樹，將該二叉搜素樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
二叉樹節(jié)點(diǎn)定義如下：

卓尼網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站設(shè)計(jì)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)2013年開創(chuàng)至今到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)。

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

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

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* pList=nullptr;//雙向鏈表的頭節(jié)點(diǎn)
        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相當(dāng)于pNext
        if (pList != nullptr)
            pList->left = pRootOfTree;//left相當(dāng)于pPre
        pList = pRootOfTree;//pList節(jié)點(diǎn)從尾結(jié)點(diǎn)依次移動(dòng)到頭節(jié)點(diǎn)
        if (pRootOfTree->left != nullptr)//遞歸處理左子樹
            Convert(pRootOfTree->left, pList);
    }
};

標(biāo)題名稱：C++二叉搜索樹與雙向鏈表（劍指Offer精簡(jiǎn)版）
轉(zhuǎn)載來(lái)源：http://chinadenli.net/article6/pddsog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁(yè)設(shè)計(jì)公司、移動(dòng)網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化、微信公眾號(hào)、ChatGPT、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)