二叉树展开为链表。
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
递归或者莫里斯遍历。
时间复杂度：O(N)。
空间复杂度：O(树的高度)。用莫里斯遍历可优化成O(1)。
代码用golang编写。代码如下：
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)
}执行结果如下：
