剑指offer 面试题36 二叉搜索树与双向链表

最新推荐文章于 2023-03-15 14:15:35 发布

wenkun97

最新推荐文章于 2023-03-15 14:15:35 发布

阅读量179

点赞数

分类专栏：剑指offer 文章标签：链表指针

本文链接：https://blog.csdn.net/hello_my_coder/article/details/104414779

版权

剑指offer 专栏收录该内容

53 篇文章

订阅专栏

本文介绍了一种不创建新节点，仅通过调整二叉搜索树节点指针指向，将其转换为排序双向链表的方法。利用递归，记录转换后链表的最后一个元素，最终返回链表头节点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

tips: 使用递归，使用一个指针的引用，来记录转换为链表后的最后一个元素

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==NULL) {
            return NULL;
        }
        TreeNode* pLast=NULL;
        cursiveConvert(pRootOfTree,pLast);
        while(pLast->left) {
            pLast=pLast->left;
        }
        return pLast;
    }
    void cursiveConvert(TreeNode* pRoot,TreeNode*& pLast) {
        if(pRoot==NULL) {
            return;
        }
        cursiveConvert(pRoot->left,pLast);
        if(pLast!=NULL) {
            pRoot->left=pLast;
            pLast->right=pRoot;
        }
        pLast=pRoot;
        cursiveConvert(pRoot->right,pLast);
    }
};