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

发布时间:2020-03-03 23:10:05 作者:梦T醒
来源:网络 阅读:249

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);
    }
};
推荐阅读:
  1. 剑指offer:二叉搜索树与双向链表
  2. 剑指offer:二叉搜索树的后序遍历序列

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

二叉搜索树 双向链表 二叉搜索树与双向链表

上一篇:MongoDB分片群集

下一篇:将AIR-CAP2702I-H-K9升级成胖AP

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》