2021-06-02: given the head node of a search binary tree, it will be transformed into an ordered two-way linked list with head and tail connected.

2021-06-02： Given a search binary tree head node , Turn into an orderly two-way linked list connected from beginning to end .

Fuda answer 2021-06-02：

Binary tree recursion . The left subtree is finished , The right subtree is finished , Eventually string yourself .

The code to use golang To write . The code is as follows ：

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
    }
    //  The head of the whole linked list     lInfo.start != null ? lInfo.start : X
    //  Tail of the whole linked list     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
    }
}

The results are as follows ：

picture

---

Zuo Shen java Code