【剑指】二叉搜索树转排序双向链表

快来打我* 2023-06-25 02:16 10阅读 0赞

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

思路：首先最小的数在极左节点，他的前一个节点为空。后一节点为其父节点。采用中序遍历将每个节点的前一个结点（会变，null开始）转换为双向的，再判断右节点，然后递归。  
最后输出的节点变到头节点。  
**注意：变换需要保留前一节点，所以这里采用给一个空的节点**

代码：

class Solution { 
    public:
        TreeNode* Convert(TreeNode* pRootOfTree)
        { 
           TreeNode* pre=nullptr;
           if(pRootOfTree==nullptr )    return pre;
           convert(pRootOfTree, pre);
            
           TreeNode* res=pRootOfTree;
            while(res->left)
                res=res->left;
            return res;
        }
        
     private:
            void convert(TreeNode* cur, TreeNode* &pre)//注意引用
            { 
                if(cur==nullptr)
                    return ;
                //中序遍历
                 convert(cur->left, pre);
                
                cur->left=pre;
                if(pre)    pre->right=cur;    //双向，前提是不为空
                pre=cur;    //指针指向得值一旦改变了，之前得指针指向也会变，即使是递归嵌套
                            //屁，只是因为用的是引用
                   convert(cur->right, pre);
                
                return;
            }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关【剑指】二叉搜索树转双向链表

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

本是古典何须时尚/ 2023年06月25日 10:12/ 0 赞/ 13 阅读

相关【剑指】二叉搜索树转排序双向链表

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。思路：首先最小的数在极左节点，他的前一个节点

快来打我*/ 2023年06月25日 02:16/ 0 赞/ 11 阅读

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

题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。空间复杂度为O(1). 最笨的方法就是中序遍历放在一个数组或链表中，再次遍历串联起来。但是要求空间

Myth丶恋晨/ 2022年08月04日 04:20/ 0 赞/ 196 阅读

相关剑指offer——二叉搜索树与双向链表

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。分析：这个题本质上其实是对二叉搜索树的中序遍历，

喜欢ヅ旅行/ 2022年05月30日 04:24/ 0 赞/ 195 阅读

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

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

一时失言乱红尘/ 2022年03月31日 04:40/ 0 赞/ 216 阅读

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

题目链接：[https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11

亦凉/ 2022年03月16日 01:06/ 0 赞/ 217 阅读

相关剑指Offer-二叉搜索树与双向链表

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。解题思路—递归：抓住二叉搜索树的本质，可以

我会带着你远行/ 2022年02月25日 10:08/ 0 赞/ 208 阅读

相关剑指offer:二叉搜索树与双向链表

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

谁践踏了优雅/ 2022年02月24日 13:35/ 0 赞/ 216 阅读

相关 [剑指offer]二叉搜索树与双向链表

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

野性酷女/ 2021年12月19日 16:07/ 0 赞/ 208 阅读

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

试题：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。代码：首先明白二叉搜索树的规律就会发现

缺乏、安全感/ 2021年06月24日 16:09/ 0 赞/ 409 阅读