将链表转换为平衡二叉树

图片.png

package main

import "fmt"

// LNode 链表的单个节点对象
type LNode struct {
    Val  int
    Next *LNode
}

// TNode 二叉树的单个节点对象
type TNode struct {
    Val   int
    Left  *TNode
    Right *TNode
}

func findMid(left *LNode, right *LNode) *LNode {
    fast := left
    slow := left

    for fast != right && fast.Next != right {
        fast = fast.Next
        fast = fast.Next
        slow = slow.Next
    }

    return slow
}

func buildTree(head *LNode, tail *LNode) *TNode {
    if head == tail {
        return nil
    }

    mid := findMid(head, tail)
    root := &TNode{Val: mid.Val}
    root.Left = buildTree(head, mid)
    root.Right = buildTree(mid.Next, tail)
    return root
}

// List2Tree 将链表转换为树的方法
func List2Tree(head *LNode) *TNode {
    return buildTree(head, nil)
}

// PrintTree 打印树结构的函数
func PrintTree(root *TNode) {
    if root == nil {
        return
    }

    fmt.Printf("%v->", root.Val)
    PrintTree(root.Left)
    PrintTree(root.Right)
}

func main() {
    head := &LNode{
        Val: -10,
        Next: &LNode{
            Val: -3,
            Next: &LNode{
                Val: 0,
                Next: &LNode{
                    Val: 5,
                    Next: &LNode{
                        Val: 9,
                    },
                },
            },
        },
    }

    root := List2Tree(head)
    PrintTree(root)
}

程序输出，

图片.png