资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

C++二叉搜索树与双向链表(剑指Offer精简版)

C++二叉搜索树与双向链表(剑指Offer精简版)题目:输入一棵二叉搜索树,将该二叉搜素树转换成一个排序的双向链表。
二叉树节点定义如下:

卓尼网站制作公司哪家好,找创新互联!从网页设计、网站建设、微信开发、APP开发、响应式网站设计等网站项目制作,到程序开发,运营维护。创新互联2013年开创至今到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联

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);
    }
};

网站名称:C++二叉搜索树与双向链表(剑指Offer精简版)
本文路径:http://cdkjz.cn/article/pddsog.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220