剑指offer面试题[27]-二叉搜索树与双向链表

一时失言乱红尘 2022-06-11 04:19 147阅读 0赞

## 题目描述 ##

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

/*
    struct TreeNode {
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
    	}
    };*/
    class Solution {
    public:
        TreeNode* Convert(TreeNode* pRootOfTree)
        {
            TreeNode* pLastNodeInList=NULL;
            ConvertNode(pRootOfTree,&pLastNodeInList);
            
            TreeNode* pHeadOfList=pLastNodeInList;
            while(pHeadOfList!=NULL&&pHeadOfList->left!=NULL)
                pHeadOfList=pHeadOfList->left;
            return pHeadOfList;
        }
        
        void ConvertNode(TreeNode* pRootOfTree,TreeNode* *pLastNodeInList)
        {
            if(pRootOfTree==NULL)
                return;
            
            TreeNode* pCurrent=pRootOfTree;
            
            if(pCurrent->left!=NULL)
                ConvertNode(pCurrent->left,pLastNodeInList);
            
            pCurrent->left=*pLastNodeInList;
            if(*pLastNodeInList!=NULL)
               (*pLastNodeInList)->right=pCurrent;
            *pLastNodeInList=pCurrent;
            
            if(pCurrent->right!=NULL)
                ConvertNode(pCurrent->right,pLastNodeInList);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer-Java版】27二叉搜索树与双向链表

二叉排序树转双向链表：又是一个不是很懂的递归，原理很懂，代码很懂，自己写就需要写很久需要多画画图，多在脑子里面模拟一下递归过程，缺乏此类训练这个递归练习也是理解Jav

拼搏现实的明天。/ 2022年08月21日 09:40/ 0 赞/ 137 阅读

相关剑指offer之面试题27二叉搜索树与双向链表

问题描述：输入一颗二叉搜索树，将该二叉搜索树转换为一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。实现代码如下： include

古城微笑少年丶/ 2022年07月24日 04:02/ 0 赞/ 117 阅读

相关剑指Offer面试题27（Java版）：二叉搜索树与双向链表

题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建新的结点，只能调整树中结点指针的指向。比如如下图中的二叉搜索树，则输出转换之后的排序双向链表为

Bertha 。/ 2022年07月16日 04:39/ 0 赞/ 133 阅读

相关剑指offer面试题[27]-二叉搜索树与双向链表

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

一时失言乱红尘/ 2022年06月11日 04:19/ 0 赞/ 148 阅读

相关【剑指offer】面试题36：二叉搜索树与双向链表

题目输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路这题看的时候一脸懵逼…思考的时候还

素颜马尾好姑娘i/ 2022年06月11日 02:23/ 0 赞/ 194 阅读

相关剑指Offer面试题27：二叉搜索树与双向链表

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

朱雀/ 2022年05月30日 12:15/ 0 赞/ 143 阅读

相关剑指offer-题27：二叉搜索树与双向链表

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。实验平台：[牛客网][Link 1] -

￡神魔★判官ぃ/ 2022年05月28日 04:50/ 0 赞/ 114 阅读

相关【剑指Offer】27二叉搜索树与双向链表

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

桃扇骨/ 2022年05月10日 18:46/ 0 赞/ 137 阅读

相关【剑指offer】面试题36：二叉搜索树与双向链表

> 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。比如如下图中的二叉搜索树，则输出转换之后的排序

约定不等于承诺〃/ 2022年04月10日 14:24/ 0 赞/ 192 阅读

相关 27. 二叉搜索树与双向链表《剑指Offer》(Java版)

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

迷南。/ 2022年01月30日 11:15/ 0 赞/ 168 阅读