图解LeetCode——剑指 Offer 36. 二叉搜索树与双向链表

简介: 图解LeetCode——剑指 Offer 36. 二叉搜索树与双向链表

一、题目

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

二、示例

  • 为了让您更好地理解问题,以下面的二叉搜索树为例:

  • 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

  • 特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

三、解题思路

  • 根据题目描述,我们要将一颗二叉搜索树转换成为一个排序的循环双向链表。这里有两个重要的信息:

信息1】这是一颗二叉搜索树,那么这个二叉树就具有Node.left.val < Node.val < Node.right.val的特点。

信息2】要构建一个排序的循环双向链表。

  • 那么针对“信息1”,我们可以采用中序遍历的方式对二叉搜索树种的各个节点执行遍历操作。那么对于中序遍历,我们采用的代码结构如下所示:
voiddfs(Nodenode) {
    ... ...
dfs(node.left); // 处理左子节点node// 处理当前节点dfs(node.right); // 处理右子节点 ... ...
}
  • 那么针对“信息2”,我们需要一个循环的双向链表,那么这个循环就需要我们创建两个指针了,即:头指针Node head和尾指针Node cur(在程序执行过程中,cur表示正在处理的那个节点,所以当整个二叉搜索树都遍历完毕后,cur就是双向链表中最末尾的那个节点了)。那么,当整个搜索二叉树都遍历完毕之后,我们就可以通过执行:head.left = curcur.right = head来将双向链表的收尾相连。
  • 上面就是整个题目的解题思路了,下面我们还是按照惯例,以输入:[4,2,5,1,3]为例,看一下具体拼装有序双向循环链表的过程是怎么样子的。请见下图所示:

四、代码实现

classSolution {
Nodehead, cur;
publicNodetreeToDoublyList(Noderoot) {
if (root==null) returnroot;
dfs(root);
head.left=cur;
cur.right=head;
returnhead;
    }
voiddfs(Nodenode) {
if (node==null) return;
dfs(node.left);
if (head==null) {
head=cur=node;
        } else {
cur.right=node;
node.left=cur;
cur=node;
        }
dfs(node.right);
    }
}


今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

相关文章
|
22天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
31 1
|
29天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
46 0
Leetcode第21题(合并两个有序链表)
|
28天前
【LeetCode 45】701.二叉搜索树中的插入操作
【LeetCode 45】701.二叉搜索树中的插入操作
9 1
|
28天前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
15 1
|
29天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
15 0
LeetCode第二十四题(两两交换链表中的节点)
|
28天前
【LeetCode 48】108.将有序数组转换为二叉搜索树
【LeetCode 48】108.将有序数组转换为二叉搜索树
34 0
|
28天前
【LeetCode 47】669.修剪二叉搜索树
【LeetCode 47】669.修剪二叉搜索树
8 0
|
28天前
【LeetCode 46】450.删除二叉搜索树的节点
【LeetCode 46】450.删除二叉搜索树的节点
11 0
|
28天前
【LeetCode 42】501.二叉搜索树中的众数
【LeetCode 42】501.二叉搜索树中的众数
8 0
|
28天前
【LeetCode 41】530.二叉搜索树的最小绝对差
【LeetCode 41】530.二叉搜索树的最小绝对差
9 0