首页 > 试题广场 >

二叉搜索树与双向链表

[编程题]二叉搜索树与双向链表

热度指数：626157 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 $0 \le n \le 1000$ ，二叉树中每个节点的值 $0\le val \le 1000$
要求：空间复杂度 $O(1)$ （即在原树上操作），时间复杂度 $O(n)$

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述:

二叉树的根节点

输出描述:

双向链表的其中一个头节点。

示例1

输入

{10,6,14,4,8,12,16}

输出

From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

说明

输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

示例2

输入

{5,4,#,3,#,2,#,1}

输出

From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;

说明

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

牛客313925129号

发表于 2021-07-14 13:34:50

精华题解方法一已知将二叉搜索树进行中序遍历可以得到由小到大的顺序排列，因此本题最直接的想法就是进行中序遍历。将中序遍历的结果用数组存储下来，得到的数组是有从小到大顺序的。最后将数组中的结点依次连接即可。示意图如下：具体代码如下： /* struct TreeNode { int val; 展开全文

牛客题解官

发表于 2022-04-22 11:57:27

精华题解题目的主要信息：将二叉搜索树转化成递增序的双向链表不能添加新的节点，要在原节点基础上添加链表链接返回链表中的第一个节点的指针二叉树节点的左右指针看成双向链表的前后指针举一反三：学习完本题的思路你可以解决如下题目： BM34. 判断是不是二叉搜索树 BM37. 二叉搜索树的最近公共祖先展开全文

Maokt

发表于 2021-07-14 15:38:24

精华题解算法思想一：中序遍历+数组解题思路：主要思想是根据二叉树的中序遍历，并将遍历结果存储到数组中，再对数组进行遍历生成双向链表 1、特殊情况，如果二叉树为空，则返回 none 2、构建辅助数组 res 存储二叉树的中序遍历结果 3、遍历数组构建双向链表展开全文

leaves0924

发表于 2021-06-22 16:47:57

精华题解题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示注意:1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继2.返回链表中的第一个节点的指针3.函数返回的TreeNode，有左右指针，其实可展开全文

NumPy

发表于 2021-06-30 13:47:37

精华题解一、题目描述 JZ26 二叉搜索树与双向链表题目大意：输入一棵二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表注意审题：1. 要求不能创建任何新的节点, 只能原地调整树中节点指针的指向(暗示我们不能够采用先存下二叉树的所有值再重新创建链表) 2. 转化完成后树中节点的左指针要指向展开全文

GhostLX

发表于 2021-07-21 16:06:28

精华题解题目陈述大意：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表算法一：算法思路不难发现，二叉搜索树（BST）的中序遍历，得到的序列，是递增的而需要的双向链表也就是利用递增序列排序的因为STL中的vector是个模板类，也就是说他不仅仅可以装整数和字符，还可以装任意类型的，所以展开全文

Peterliang

发表于 2021-06-23 21:23:54

精华题解题意分析给出一棵二叉树，我们需要按照这棵树的节点的权值的大小先进行升序排序，然后在不改新增节点的前提下将它改为一条双向链表。原来的左指针作为一个前驱指针，右指针作为一个后继指针。思路分析解法一对于这个题目，一开始想的是用一个map存储每个数字对应的一个节点，这种的思路其实是有问题的展开全文

蒙牛麦片

发表于 2021-06-24 09:48:06

精华题解 jz 26 题意描述题目大意：将二叉搜索树转换成一个双向链表基础知识：二叉搜索树（BST），它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排展开全文

MeteorChen

发表于 2020-03-16 16:53:05

方法1 首先最容易想到的，是用一个数组来存储中序遍历的节点，然后再从头到尾，建立节点前后的连接关系。代码如下： import java.util.ArrayList; public class Solution { public TreeNode Convert(TreeNode pRoot 展开全文

超级大妖怪

发表于 2019-08-13 22:26:23

我的思路是这样，中序遍历二叉树，然后用一个ArrayList类保存遍历的结果，这样在ArratList中节点就按顺序保存了，然后再来修改指针，虽然没有一点技术含量，但是最后竟然还通过了哈哈哈。。。 public TreeNode Convert(TreeNode pRootOfTree) { 展开全文

每天刷刷牛客网

发表于 2019-09-13 17:18:24

public class Solution { TreeNode pre=null; public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree==null) return nul 展开全文

ZwZ呀咿呀咿哟

发表于 2020-01-27 16:39:16

(不开辟新的存储空间来完成二叉排序树向双向链表的转换)大致思路：在中序遍历的过程中对每个节点的指针进行操作：完成对二叉排序树中元素从小到大的排序并且对每个遍历到的节点的指针进行修改。 **** 借助一个指针指向每次遍历到的节点，下一次中序遍历到的节点的前驱便是此指针指向的节点，而此节点的后序是展开全文

ZhangHao0810

发表于 2021-07-20 21:55:51

这道题真的很拿人二叉搜索树，做边一直递归，要有一个前驱pre节点。递归到上一级的时候 root 就是pre的后继。最终若返回pre，那么是降序排列，题干要求升序，故保存第一个节点，返回第一个节点。【多练，多尝试。】 public class Solution { TreeNode p 展开全文

c7rious

发表于 2019-11-28 09:58:19

class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if (pRootOfTree == nullptr) return pRootOfTree; 展开全文

我要来面试

发表于 2019-09-22 10:02:43

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # &n 展开全文

心谭

发表于 2020-02-08 14:03:54

【二叉搜索树与双向链表】【2种解法（一次递归或递归+遍历）】题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。解法 1: 一次递归（推荐）二叉搜索树的性质是：左节点 < 当前节点 < 右节点。转换后的双向展开全文

designeer

发表于 2021-11-06 16:04:50

思路： # 先中序遍历，将所有的节点保存到一个列表中。对这个list[:-1]进行遍历， # 每个节点的right设为下一个节点，下一个节点的left设为上一个节点。 class Solution: def&nbs 展开全文

一叶浮尘

发表于 2019-08-17 10:10:07

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。第一眼看到题目感觉不是非常地有思路，这题目到底在考什么呢？这真的是我曾经刷过的题目吗？一点印象都没有 import java.util.List; import java.util.A 展开全文

问题信息

分治

难度：

1293条回答 5486收藏 153062浏览

通过挑战的用户

查看代码

牛客39358...

2023-03-13 14:57:19
Elastic...

2023-02-26 14:54:56
随机昵称都有什...

2023-02-20 18:19:11
想笑

2023-02-20 15:17:25
想吃卤蛋的99...

2023-01-09 14:39:12