给定一棵搜索二叉树头节点，转化成首尾相接的有序双向链表。
二叉树递归。左子树串完，右子树串完，最终串自己。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
head := &Node{Val: 5}
head.Left = &Node{Val: 3}
head.Left.Left = &Node{Val: 1}
head.Left.Right = &Node{Val: 4}
head.Right = &Node{Val: 7}
head.Right.Left = &Node{Val: 6}
head.Right.Right = &Node{Val: 8}
ret := treeToDoublyList(head)
for i := 0; i < 20; i++ {
fmt.Println(ret)
ret = ret.Right
}
}
type Node struct {
Val int
Left *Node
Right *Node
}
func treeToDoublyList(head *Node) *Node {
if head == nil {
return nil
}
allInfo := process(head)
allInfo.End.Right = allInfo.Start
allInfo.Start.Left = allInfo.End
return allInfo.Start
}
type Info struct {
Start *Node
End *Node
}
func process(X *Node) *Info {
if X == nil {
return &Info{}
}
lInfo := process(X.Left)
rInfo := process(X.Right)
if lInfo.End != nil {
lInfo.End.Right = X
}
X.Left = lInfo.End
X.Right = rInfo.Start
if rInfo.Start != nil {
rInfo.Start.Left = X
}
// 整体链表的头 lInfo.start != null ? lInfo.start : X
// 整体链表的尾 rInfo.end != null ? rInfo.end : X
return &Info{twoSelectOne(lInfo.Start != nil, lInfo.Start, X), twoSelectOne(rInfo.End != nil, rInfo.End, X)}
}
func twoSelectOne(c bool, a *Node, b *Node) *Node {
if c {
return a
} else {
return b
}
}执行结果如下：
