专栏首页全部文章Day26:二叉搜索树与双向链表

Day26:二叉搜索树与双向链表

剑指Offer_编程题——二叉搜索树与双向链表

题目描述:

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

具体要求:

时间限制: C/C++ 1秒,其他语言2秒 空间限制: C/C++32M,其他语言64M

具体思路:

背景知识介绍   在做该题之前,我们应该首先了解二叉搜索树,详细解释请看本文。接下来,还需要我们了解二叉树的中序遍历,因为我们做本题最关键的思想就是二叉树的中序遍历。在维基百科中,树的中序遍历为:指先访问左(右)子树,然后访问根,最后访问右(左)子树的遍历方式。例如在以下的树中:

其中序遍历的顺序为:A B C D E F G H I。这就是中序遍历。最后还需要掌握双链表的相关知识。在维基百科中,双向链表是这样解释的:双向链表,又称为双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。以下就是一个双向链表

  根据题目可知:如果有以下的一颗树:

转换成相应的双向链表为:

具体思路:   根据我们理解的题意以及之前介绍的搜索二叉树和二叉树的中序遍历可知,二叉搜索树的中序遍历刚好是从小到大排序。因此本题的核心就是二叉搜索树的中序遍历,然后我们可以将遍历的结果存放在链表中。本题的关键是如何将左子树的最大值与右子树的最小值通过根root连接起来。比如题目中的8和12.这也是解决本题最为核心的部分。本题由于是二叉搜索树,因此有会用到我们的递归算法。其实应用递归需要我们理解递归进入的条件、递归返回的状态,如果递归进入时改变了环境,返回时应当恢复环境,就像栈的操作一样。在使用指针变量的时候一定要进行初始化,本题有一个小坑就是返回的不是表头而是root。具体我们可以用java和python来实现该思路。 1、首先用java来实现

public class Solution{
	public static TreeNode Convert(TreeNode pRootOfTree){
		TreeNode lastNode = null;
		TreeNode headNode = ConvertNode(pRootOfTree, lastNode);
		while(headNode != null && headNode.left != null){
			headNode = headNode.left;
		}
		return headNode;
	}
	public static TreeNode ConvertNode(TreeNode rootTree, TreeNode lastNode){
		if(rootTree == null){
			return null;
		}
		if(rootTree.left != null){
			lastNode = ConvertNode(rootTree.left, lastNode);
		}
		rootTree.left = lastNode;
		if(lastNode != null){
			lastNode.right = rootTree;
		}
		lastNode = rootTree;
		if(rootTree.right != null){
			lastNode = ConvertNode(rootTree.right, lastNode);
		}
		return lastNode;
	}
}

代码效果图如图所示:

正如前面提到一样,牛客网已经为我们定义了节点,不需要我们重复定义,但是在自己的本地编译器中,我们需要定义节点TreeNode的类,具体实现如下:

public class TreeNode{
	int val = 0;
	TreeNode left = null;
	TreeNode right = null;
	public TreeNode(int val){
		this.val = val;
	}
}

2、接下来用python将其实现

class Solution:
	def Convert(self, pRootOfTree):
		self.linkedlistLast = None
		self.convertNode(pRootOfTree)
		pHead = self.linkedlistLast
		while pHead and pHead.left:
			pHead = pHead.left
		return pHead
	def convertNode(self, root):
		if not root:
			return
		pcurr = root
		if pcurr.left:
			self.convertNode(pcurr.left)
		pcurr.left = self.linkedlistLast
		if self.linkedlistLast:
			self.linkedlistLast.right = pcurr
		self.linkedlistLast = pcurr
		if pcurr.right:
			self.convertNode(pcurr.right)

代码效果图如图所示:

用python实现树结构:

class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

总结

  本道题主要二叉搜索树以及二叉树的中序遍历还有就是递归和双向链表。在解题之前我们给大家介绍了二叉搜索树、二叉树的中序遍历以及双向链表的基本知识,并且还给出了解题的思路,应用java和python两门语言将其实现,其实本题的关键就是中序遍历,还有一个小坑就是本题返回的不是链表表头,而是根节点。因此,我们需要深刻掌握树的相关实现,尤其是二叉树,并且也要掌握数据结构相关的知识,只有这样,才能遇到综合性问题做到融会贯通,写出优质的代码。总之,我们要继续加油,争取早日找到工作,Good Luck!!!

参考文献

[1] qq_23217629 [2] 负雪明烛 [3] 二叉搜索树 [4] 二叉树的中序遍历 [5] 双向链表

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day15:反转链表

    背景知识介绍   在做本题之前首先介绍一下链表的基本知识。在维基百科中,链表 是这样定义的:链表(Linked list)是一种常见的基础数据结构,是一种线...

    stefan666
  • Day62:二叉搜索树的第k个结点

    背景知识介绍:   在前面的文章中我们详细的介绍了二叉搜索树的相关概念,接下来我们介绍二叉搜索树的具体应用。二叉排序树又称二叉查找树(二叉搜索树),它或是一棵...

    stefan666
  • 数据结构(五)——链表

      上篇文章我们给大家介绍了队列,主要包括稀疏数组的含义以及相关二者之间的转换思路和及其实现,之后又介绍了队列的基本思想和用数组来模拟队列将其进行实现,通过模拟...

    stefan666
  • FreeRTOS 任务调度 List 组织

    前面了解了 FreeRTOS 的内存管理,接下来看看任务调度,这也是一个操作系统中最重要的一部分,而其任务调度大量使用了链表(list.c 实现),调度器使用链...

    orientlu
  • 一起刷题(leetcode)第二篇:如何用Python实现递归

    我们知道递归是一类比较巧妙但是理解难度有点大的算法,对于工作中需要用到数据结构和高级算法的人需要牢固掌握递归算法。今天就以实际的案例来带大家一起学习和理解如何用...

    HuangWeiAI
  • 环形链表

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(...

    _kyle
  • Innodb Buffer Pool的三种Page和链表

    Buffer Pool 是Innodb 内存中的的一块占比较大的区域,用来缓存表和索引数据。众所周知,从内存访问会比从磁盘访问快很多。为了提高数据的读取速度,B...

    用户1278550
  • 【干货】20K以上的高薪Java必掌握的基础知识点(二)

    怎么样!上一期的知识点小伙伴都掌握了多少呢?复习的同时有没有查漏补缺的巩固自己的基础知识呢?今天我们来复习Java基础知识第二期! 61、Math 类提供了许多...

    老九君
  • 商业5G网络架构比较:KT与SK Telecom

    本文分析了KT和SK Telecom的商业5G网络建设的现状,以及各自所追求的5G价值的差异。

    SDNLAB
  • LeetCode | 94.二叉树的中序遍历

    这次来写一下 LeetCode 的第 94 题,二叉树的中序遍历。

    码农UP2U

扫码关注云+社区

领取腾讯云代金券