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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++二叉搜索树与双向链表（剑指Offer精简版），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1028字，纯文字阅读大概需要2分钟。

内容图文

题目：输入一棵二叉搜索树，将该二叉搜素树转换成一个排序的双向链表。
二叉树节点定义如下：

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精简版）全部内容，希望文章能够帮你解决C++二叉搜索树与双向链表（剑指Offer精简版）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端