樹13--序列化二叉樹

樹13--序列化二叉樹-jz61

• ​​題目概述​​
• ​​解析&參考答案​​
• ​​注意事項​​
• ​​說明​​

題目概述

• 算法說明

  請實作兩個函數，分别用來序列化和反序列化二叉樹

  二叉樹的序列化是指：把一棵二叉樹按照某種周遊方式的結果以某種格式儲存為字元串，進而使得記憶體中建立起來的二叉樹可以持久儲存。序列化可以基于先序、中序、後序、層序的二叉樹周遊方式來進行修改，序列化的結果是一個字元串，序列化時通過 某種符号表示空節點（#），以 ！ 表示一個結點值的結束（value!）。

  二叉樹的反序列化是指：根據某種周遊順序得到的序列化字元串結果str，重構二叉樹。

  例如，我們可以把一個隻有根節點為1的二叉樹序列化為"1,"，然後通過自己的函數來解析回這個二叉樹。

• 測試用例

  輸入：

  {8,6,10,5,7,9,11}

  輸出：

  {8,6,10,5,7,9,11}

  輸入：

  {5,4,#,3,#,2}

  輸出：

  {5,4,#,3,#,2}

解析&參考答案

• 解析

1. 按照指定的方式序列化，此處對葉子節點的左右節點都用#來表示(與牛客上的思路有一點差別)。

• 參考答案

vim jz61.go
package main

import (
    "fmt"
    "strconv"
    "strings"
)

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

func Serialize(root *TreeNode) *TreeNode {
    return &TreeNode{}
}

func SerializePre(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    ret := ""
    ret = ret + strconv.Itoa(root.Val) + "," + SerializePre(root.Left) + "," + SerializePre(root.Right)
    return ret
}

var index = -1

func DeSerializePre(str []string) *TreeNode {
    index++
    if index > len(str) {
        return nil
    }
    v := str[index]
    if v != "#" {
        value, _ := strconv.Atoi(v)
        root := &TreeNode{value, nil, nil}
        root.Left = DeSerializePre(str)
        root.Right = DeSerializePre(str)
        return root
    } else {
        return nil
    }
}

func main() {
    root := &TreeNode{10, &TreeNode{5, &TreeNode{4, nil, nil}, &TreeNode{7, nil, nil}},
        &TreeNode{12, nil, nil}}
    treeStr := SerializePre(root)
    fmt.Println(treeStr)
    newRoot := DeSerializePre(strings.Split(treeStr, ","))
    fmt.Println(SerializePre(newRoot))
}      

注意事項

1. 牛客網中若某個節點是葉子節點，那麼不設定#辨別符号，若某個節點的的左或右節點為空，那麼設定為#，其對應的案例2似乎有點問題。

說明

1. 目前使用 go1.15.8
2. 參考​​牛客網--劍指offer​​ 标題中jzn(n為具體數字)代表牛客網劍指offer系列第n号題目，例如 jz01 代表牛客網劍指offer中01号題目。

• 筆者最近在學習 golang，是以趁機通過資料結構和算法來進一步熟悉下go語言
• 目前算法主要來源于劍指 offer，後續會進一步補充 LeetCode 上重要算法，以及一些經典算法
• 此處答案僅為參考，不一定是最優解，歡迎感興趣的讀者在評論區提供更優解