2021-12-09:二叉树展开为链表。 给你二叉树的根结点 roo
2023-04-18 15:02:40 时间
2021-12-09:二叉树展开为链表。
给你二叉树的根结点 root ,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
力扣114。
答案2021-12-09:
递归或者莫里斯遍历。
时间复杂度:O(N)。
空间复杂度:O(树的高度)。用莫里斯遍历可优化成O(1)。
代码用golang编写。代码如下:
```go
package main
import "fmt"
func main() {
head := NewTreeNode(1)
head.left = NewTreeNode(2)
head.right = NewTreeNode(3)
head = convert(head)
for head != nil {
fmt.Println(head.val)
head = head.right
}
}
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func NewTreeNode(value int) *TreeNode {
ret := &TreeNode{}
ret.val = value
return ret
}
func convert(head *TreeNode) *TreeNode {
if head == nil {
return nil
}
return process(head).head
}
type Info struct {
head *TreeNode
tail *TreeNode
}
func NewInfo(h, t *TreeNode) *Info {
res := &Info{}
res.head = h
res.tail = t
return res
}
func process(x *TreeNode) *Info {
if x == nil {
return nil
}
leftInfo := process(x.left)
rightInfo := process(x.right)
// 2...4 5 6...13
if leftInfo != nil {
leftInfo.tail.right = x
x.left = leftInfo.tail
}
if rightInfo != nil {
x.right = rightInfo.head
rightInfo.head.left = x
}
var head *TreeNode
if leftInfo != nil {
head = leftInfo.head
} else {
head = x
}
var tail *TreeNode
if rightInfo != nil {
tail = rightInfo.tail
} else {
tail = x
}
return NewInfo(head, tail)
}
```
执行结果如下:
![图片](https://img-blog.csdnimg.cn/5adb05e1ca67492897c2495933a49dc0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56aP5aSn5aSn5p625p6E5biI5q-P5pel5LiA6aKY,size_18,color_FFFFFF,t_70,g_se,x_16)
[左神java代码]( https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class37/Problem_0114_FlattenBinaryTreeToLinkedList.java)
相关文章
- LeetCode 1637. 两点之间不包含任何点的最宽垂直面积
- Linux虚拟化KVM-Qemu分析之Vhost-Net
- LeetCode 1561. 你可以获得的最大硬币数目
- 阅读一个分布式框架,这些必备的 NIO 知识你要知道
- 2021年新基建项目火热开局:5G基站、大数据中心、工业互联网等成重点
- LeetCode 950. 按递增顺序显示卡牌
- Gartner:2021年全球公有云支出将达3323亿美元
- LeetCode 1329. 将矩阵按对角线排序
- LeetCode 1859. 将句子排序
- 上调预期:Gartner预测21年全球公有云终端用户支出增长23%
- 蚂蚁金服、京东科技们的新出路
- LeetCode 406. 根据身高重建队列
- LeetCode 1502. 判断能否形成等差数列
- Gartner预测2021年全球公有云终端用户支出将增长23%,中国增长达62.1%
- LeetCode 1356. 根据数字二进制下 1 的数目排序
- 40亿美元,戴尔同意出售云业务Boomi
- 共建共享700MHz5G网络中国移动与中国广电启动战略合作
- LeetCode 977. 有序数组的平方
- Canalys:全球云计算支出达到418亿美元
- 不同价格5G套餐,不同网速!原来5G也分三六九等?