葡京娱乐开元棋牌_开元棋牌靠谱吗_f1娱乐开元棋牌先锋网 葡京娱乐开元棋牌_开元棋牌靠谱吗_f1娱乐开元棋牌片段及技术文章聚合

剑指offer----二叉树转双向链表

技术标签: 二叉树  双向链表

这里写图片描述
思路:

将二叉搜索树转化为有序双向链表,因为二叉搜索树是有规律的,所以类似于中序遍历,中序遍历的结果是有序的(升序)。

首先找到双向链表的头结点,以便以后找到该链表,返回该链表的头指针。该程序是采用递归的,找到根结点的左子树的最后一个结点,对根结点的左右指针进行修改,使得具有双向链表的性质,即和左子树的最后一个结点互相指向。到这里,根结点前面的结点全都变为双向循环链表,我们需要对最后一个结点左子树的最后一个结点进行更新,将其指向后走到根结点,如果根结点有右子树,对右子树进行链表转换。
这里写图片描述

最终的结构图:
这里写图片描述

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* pLastNode = NULL;//指向双向链表的尾结点
        ConvertNode(pRootOfTree, &pLastNode);

        TreeNode* pHead = pLastNode;
        while (pHead != NULL&&pHead->left != NULL)//找到头结点,返回
            pHead = pHead->left;

        return pHead;
    }

    void ConvertNode(TreeNode* pNode, TreeNode** pLastNode)
    {
        if (pNode == NULL)
            return;

        TreeNode* pCur = pNode;
        if (pCur->left != NULL)
            ConvertNode(pCur->left, pLastNode);
        //走到这,当前结点的左子树已经转换好了,pLastNode指向左子树中的最后一个结点

        //用pLastNode指向已经转换好的链表的最后一个结点
        pCur->left = *pLastNode;
        if (*pLastNode != NULL)
            (*pLastNode)->right = pCur;

        //将pLastNode指向当前结点
        *pLastNode = pCur;
        if (pCur->right != NULL)
            ConvertNode(pCur->right, pLastNode);
    }
};

原文地址:剑指offer----二叉树转双向链表