vlambda博客
学习文章列表

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 }}