雅乐网

计算机技术、学习成长

编程 » OJ刷题 » 【OJ】二叉搜索树转换为有序双向链表

【OJ】二叉搜索树转换为有序双向链表

剑指Offer面试题27题:二叉搜索树与双向链表

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

例如:

调整之后,节点的left指针相当于链表中的pred指针,节点的right指针相当于链表中的next指针。

在线提交代码网址:二叉搜索树与双向链表

二叉搜索树节点的定义

解法1:中序遍历

对二叉搜索树进行中序遍历,节点的访问顺序正好就是有序的,也是最终得到的链表的顺序。要按照访问次序把节点连接起来,我们需要一个记录上一个节点的指针。这样,访问一个节点时,我们把上一个节点和目前访问的节点连接起来。

版本1:由中序遍历修改

中序遍历的思路为:递归处理左子树, 访问节点,递归处理右子树。我们需要修改的部分就是访问节点的代码,在访问时,把上一个节点和访问的节点链接起来。我们的递归函数如下:

这个help函数,用于处理root为根的树,变为有序链表。第二个参数pred记录上一个访问的节点。

首先处理递归基,当root为空的时候,表示这个子树为空,不需要任何操作,直接返回。

接下来,按照中序遍历的思路,先递归处理左子树

得益于递归的机制,第6行运行完毕后,左子树转换完毕,并且pred记录了上一个访问的节点。而我们马上就要访问的是root节点了,所以,接下来只要把他们(pred和root)连接到一起。

这样pred和root节点就连接到了一起,root节点访问完毕。下面要更新上次访问的节点pred 为 root,这样,下次访问某个节点的时候pred就是记录上一个节点了

最后,递归处理右子树

这样,help函数就写完了。最后写一个调用他的函数来实现题目需要的功能:

版本2:中序遍历+建立链表分离

来自 知乎@Vichare Wang

中序遍历的代码:

在visit函数里完成当前访问节点和上一个访问节点的连接,同样需要visit函数里面有一个记录上一个访问节点pred的变量。

方法2:递归

help函数的功能是把root为根的树变为链表,同时返回链表的头节点和尾节点(通过引用参数返回)

void help(TreeNode * root, TreeNode * & first, TreeNode * & last)

递归处理左子树后,把根节点和左子树链表的尾节点连接。

递归处理右子树后,把根节点和右子树链表的头节点相连。

由于first和last都是引用类型,在所有递归过程中他们只有一个,因此需要在函数中使用额外变量保存每次递归调用时的first和last。

下面的版本利用返回值返回头节点和尾节点,来自 知乎@zearom32

 

 

 

 

如果文章对你有帮助,欢迎点赞或打赏(金额不限)。你的打赏将全部用于支付网站服务器费用和提高网站文章质量,谢谢支持。

版权声明:

本文由 原创,商业转载请联系作者获得授权。
非商业转载请注明作者 雅乐网 ,并附带本文链接:
http://www.yalewoo.com/oj_binary_tree_to_linked_list.html

上一篇:

下一篇:

文章《【OJ】二叉搜索树转换为有序双向链表》共有1条评论:

我要评论

验证码*: 6 + 3 =