【剑指Offer】36. 二叉搜索树与双向链表

叁歲伎倆 2022-11-29 00:55 139阅读 0赞

[NowCoder][]

## 题目描述 ##

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70_pic_center]

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
    public class Solution { 
        // pre->cur,head为链表头。
        TreeNode head, pre;
        public TreeNode Convert(TreeNode root) { 
            dfs(root);
            return head;        
        }
        private void dfs(TreeNode cur) { 
            // 终止条件
            if(cur == null) return;
            
            // 左节点
            dfs(cur.left);
            // 根节点
            // 如果pre遍历到末端
            if(pre != null) pre.right = cur;
            else head = cur;
            cur.left = pre;
            pre = cur;
            // 右节点
            dfs(cur.right);
        }
    }

[NowCoder]: https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&tqId=11179&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=bennyrhys@163.com
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/2866500e1d114ce2a6e938f0f71fabf1.png

发表评论取消回复

表情：

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

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

相关阅读

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

剑指 Offer 36. 二叉搜索树与双向链表解题思路代码解题思路排序链表：节点应从小到大排序，因此应使用中序遍历 “从小到大”访问

￡神魔★判官ぃ/ 2023年10月05日 21:09/ 0 赞/ 49 阅读

相关《剑指Offer》36：二叉搜索树与双向链表

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

绝地灬酷狼/ 2022年12月08日 14:25/ 0 赞/ 174 阅读

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

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

叁歲伎倆/ 2022年11月29日 00:55/ 0 赞/ 140 阅读

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

题目输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。为了让您更好地理解问题，以下面的二叉搜索树

约定不等于承诺〃/ 2022年11月20日 11:59/ 0 赞/ 161 阅读

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

梦里梦外;/ 2022年10月29日 03:11/ 0 赞/ 152 阅读

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

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

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

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

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

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

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

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

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

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

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

女爷i/ 2021年12月19日 04:21/ 0 赞/ 267 阅读

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

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

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