バイナリツリーをシリアル化し、逆シリアル化する

何?
二分木は木のデータ構造であり、各ノードは2人の子を持つ.そうかも知れないかなり多くの方法で便利です.
この記事では、Golangを使ってバイナリツリーをシリアル化し、逆シリアル化しようとします.

なぜ?
オリジナルの目的はかなりprosaicです:leetcodeのバイナリ木問題の束はいくつかのテストを必要とします.しかし、“手で”木の定義はとても迷惑です.そこで、オリジナルのLeetCode入力形式を使用するには、私たち自身のシリアル化を行います.

どうやって?
始めましょうTreeNode 定義.それはノードとなるでしょうInt 値ですが、ここで必要な任意の型を使用できます.

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
} 

基本的には木を作り始める必要がある.例えば、単純なツリーを取ります.

コードを作成するには、root ノードを再帰的に定義します.

root := &TreeNode{
    Val: 1,
    Left: &TreeNode{
        Val:   2,
        Left:  nil,
        Right: nil,
    },
    Right: &TreeNode{
        Val: 3,
        Left: &TreeNode{
            Val:   4,
            Left:  nil,
            Right: nil,
        },
        Right: &TreeNode{
            Val:   5,
            Left:  nil,
            Right: nil,
        },
    },
}

ちょっと乱雑に見えます、そして、それはあなたの手でこれのような木に注釈を付けることに非常に迷惑です.あなたのデータにシリアル化を実装する多くの理由の1つになります.

直列化する
まず、木の便利な表現方法を見つけたい.シリアル化は一般的にバイトデータにエンコードするプロセスです.私たちがこれをする方法を得たとき、テストのために、または、ウェブを通してプログラムの間で木を輸送するために、ストリングデータのような木を保存することができます.

レベル順序バイナリツリー横断
LeetCodeバイナリツリー形式をサポートするには、「行単位で」シリアル化する必要があります.

我々は、使用することでこれを行うことができますLevel Order Binary Tree Traversal どちらが使用方法ですかBreadth first search アルゴリズム.
主なアイデアは、“行ごとに”ツリーを通過し、各線横断の結果を蓄積することです.
簡単な待ち行列アプローチでこれを再帰的に行うことができた.まず、キューを定義しましょう.

type NodeQueue []*TreeNode

func (q *NodeQueue) IsEmpty() bool           { return len(*q) == 0 }
func (q *NodeQueue) Push(nodes ...*TreeNode) { *q = append(*q, nodes...) }
func (q *NodeQueue) Pop() *TreeNode {
    if !q.IsEmpty() {
        n := (*q)[0]
        *q = (*q)[1:]
        return n
    }
    return nil
}

我々は、レベルで我々のノードレベルを収集したい.つまり、我々はできるはずです.

Push キュー内のノード(もう少し便利にするには、一度にいくつかのノードをプッシュすることができます).

Pop キューからのノード

知っているIsEmpty .

次に、再帰的に書くbfs 関数はすべてのノードの値を「行単位」で収集します.

const EmptyNodeMark = "null"

func bfs(q *NodeQueue) []string {
    if q.IsEmpty() {
        return nil
    }

    var (
        nextQ        NodeQueue
        level        []string
    )

    for !q.IsEmpty() {
        n := q.Pop()
        if n != nil {
            level = append(level, strconv.Itoa(n.Val))
            nextQ.Push(n.Left, n.Right)
        } else {
            level = append(level, EmptyNodeMark)
        }
    }

    return append(level, bfs(&nextQ)...)
}

いつものように、再帰関数を扱うとき、ターミネータから始めます.この場合、キューが空の場合は呼び出しを中断したいと思います.
次に、それぞれのコールに対して2つの主要な目標があります.

現在のキュー内のすべてのノードの値を収集します

次の反復(次のレベル)の次のキューをビルドします.

の初期呼び出しbfs を含むキューにroot 木の.例ではノード1です.
したがって、現在のキューからノードをポップし、それが空でない場合、level スライス.
次に、すべてのノードの子を現在のキューからnextQ スライス.ノード1はノード2とノード3となる.
現在のキューq 空になると、次のステップを取ることができますnextQ .
したがって、現在のキューは[2, 3] 我々の結果アキュムレータは"1" . 次の繰り返しの後、次のキューになる[nil, nil, 4, 5] 結果のアキュムレータ["1", "2", "3"] .
など.

しかし、問題は、ツリーの形状とは独立して、最後のレベルは常にのみ"null" 値.例では[ nil, nil, nil, nil ] .
特にシリアライズについて話しているときには、最終的な結果に不要な冗長データを含めるべきではありません.ちょっとやり直しましょうbfs .
我々は、“最後のレベル”を検出し、この場所での割り込みコールは、データの無駄な部分を含むことなく.

const EmptyNodeMark = "null"

func bfs(q *NodeQueue) []string {
    var (
        nextQ        NodeQueue
        level        []string
        isEmptyLevel = true
    )

    for !q.IsEmpty() {
        n := q.Pop()
        if n != nil {
            level = append(level, strconv.Itoa(n.Val))
            nextQ.Push(n.Left, n.Right)
            isEmptyLevel = false
        } else {
            level = append(level, EmptyNodeMark)
        }
    }

    if isEmptyLevel {
        return nil
    }

    return append(level, bfs(&nextQ)...)
}

閉じるこの動画はお気に入りから削除されています.今、我々は実装することができますStringer インターフェイスTreeNode .

const (
    EmptyNodeMark = "null"
    Separator     = ","
)

func (t TreeNode) String() string { return t.serialize() }

func (t TreeNode) serialize() string {
    data := bfs(&NodeQueue{&t})

    // remove redundant nulls
    i := len(data) - 1
    for data[i] == EmptyNodeMark {
        i--
    }

    return fmt.Sprintf("[%s]", strings.Join(data[:i+1], Separator))
}

こちらでserialize() メソッドは、コンマ区切りですべてのノードの値を連結します.

逆シリアル化する
シリアライズを行うので、逆の操作を行う必要があります.少しよりトリッキーになるつもりですが、メインのアイデアはまだ同じです.
まず、実際のツリーを構築するためにシリアル化されたデータを準備する必要があります.例からの木の直列化表現は"[1,2,3,null,null,4,5]" . 錆を上げましょう!ブラケットと文字列スライスをビルドします.

nodes := strings.Split(
    strings.TrimSuffix(strings.TrimPrefix(data, "["), "]"),
    Separator,
)

今のところ、我々は入力としてストリングスライスを得ました、そして、我々はそれから全部の木を構築する必要があります.
最初のステップとして、我々はroot を使用して、data ルート値のようにスライスします.次に、我々は移動するつもりですdata スライステールとツリーを再帰的にビルドします.ここではまだキューと同じbfsアルゴリズムです.

const EmptyNodeMark = "null"

func bfsBuild(q *NodeQueue, data []string) error {
    if len(data) == 0 || q == nil {
        return nil
    }

    var nextQ NodeQueue

    for !q.IsEmpty() {
        n := q.Pop()
        if n != nil {
            // if the data tail of current level contains only nulls, they could be reduced.
            // that means, if the data becomes empty earlier than level does, there is no more nodes
            if len(data) == 0 {
                return nil
            }
            l, r := data[0], data[1]
            data = data[2:]

            if l != EmptyNodeMark {
                if lVal, lErr := strconv.Atoi(l); lErr == nil {
                    n.Left = &TreeNode{Val: lVal}
                } else {
                    return lErr
                }
            }

            if r != EmptyNodeMark {
                if rVal, rErr := strconv.Atoi(r); rErr == nil {
                    n.Right = &TreeNode{Val: rVal}
                } else {
                    return rErr
                }
            }

            nextQ.Push(n.Left, n.Right)
        }
    }

    return bfsBuild(&nextQ, data)
}

最初の値をdata スライス、このスライスの長さは常にである必要があります.二進木とすべての非NILノードのために、2つの子供(NILノードを含む)を保証しました.したがって、各反復子はキュー内のすべての非nilノードに対して子を作り、この目的のために抽出しますlen(q) * 2 からの要素data スライス.までdata 空になる.
それだ!今マージすることができますdata における構文解析とツリー構築関数TreeNode コンストラクタ.

func NewTreeNode(data string) (*TreeNode, error) {
    if len(data) < 2 {
        return nil, errors.New("invalid input")
    }
    nodes := strings.Split(
        strings.TrimSuffix(strings.TrimPrefix(data, "["), "]"),
        Separator,
    )
    rootVal, err := strconv.Atoi(nodes[0])
    if err != nil {
        return nil, err
    }

    root := &TreeNode{Val: rootVal}
    err = bfsBuild(&NodeQueue{root}, nodes[1:])
    if err != nil {
        return nil, err
    }
    return root, nil
}

トレノードパッケージ
言うまでもなく、あなたはrepoですべてのこのコードを見つけることができました:https://github.com/egregors/TreeNode
さらに、このパッケージをLeetCodeのバイナリツリーの問題に対処するための依存関係として使用することもできます.