乐趣区

关于java:二叉搜索树转换为单向链表interview1712

题目形容

二叉树数据结构 TreeNode 可用来示意单向链表(其中 left 置空,right 为下一个链表节点)。实现一个办法,把二叉搜寻树转换为单向链表,要求仍然合乎二叉搜寻树的性质,转换操作应是旧址的,也就是在原始的二叉搜寻树上间接批改。
返回转换后的单向链表的头节点。

示例:

输出:[4,2,5,1,3,null,6,0]
输入:[0,null,1,null,2,null,3,null,4,null,5,null,6]

解题思路

二叉排序树:
1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;3、它的左、右子树也别离为二叉排序树
#### 思路一:应用递归,中序遍历,先右边,再解决,再左边
#### 思路二:借用哨兵,依然应用递归
#### 思路三:应用迭代 + 栈

语言累计和技巧

应用了前置节点来升高逻辑的解决难度
哨兵的应用

代码链接

https://github.com/lunaDolphi…
https://github.com/lunaDolphi…
https://github.com/lunaDolphi…

退出移动版