【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Unfamiliar to the tree friend, can see the front of the basic training problem oh!

  • Sequential traversal in a binary tree – iteration, recursion

  • Binary tree before sequential traversal – iteration, recursion

  • Binary tree after sequential traversal – iteration, recursion

  • Sequence traversal of binary tree – iteration, recursion

  • Maximum depth of binary tree – iteration, recursion

  • Symmetric binary tree of binary tree – iteration, recursion

  • Binary tree path summation | Go theme month – iteration, recursion

  • Construct binary tree | Go theme month by traversing sequence from middle order to back order

  • Recent common ancestor of binary tree | Go theme month

Leecode 297. Serialization and deserialization of binary trees

Serialization is the operation of converting a data structure or object into consecutive bits, which can then be stored in a file or memory, or transferred over the network to another computer environment, where the original data can be reconstructed in the reverse way.

Please design an algorithm to implement binary tree serialization and deserialization.

There is no limit to the logic that your sequence/deserialization algorithm performs, you just need to ensure that a binary tree can be serialized

Is a string and deserializes the string into the original tree structure.

Tip: The input and output formats are the same as LeetCode currently uses, see LeetCode’s Serialized binary tree format for details. You don’t have to go this way, you can solve the problem in other ways.

 

Example 1:

Enter: root = [1,2,3,null,null,4,5]

Output: [1, 2, 3, null, null, 4, 5)

Example 2:

Enter: root = []

Output: []

Example 3:

Enter: root = [1]

Output: [1]

Example 4:

Input: root = [1,2] output: [2]

Tip:

The number of nodes in the tree is within the range [0, 104]

-1000 <= Node.val <= 1000

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

GO language version of recursion

  1. You know, this is a tree, it’s just represented as an array

    Let’s take this tree as an example

Key points:

The binary tree can be traversed sequentially, serializing to None if it encounters an empty subtree, or continuing recursively. So how do we deserialize? First, we need to divide the original sequence according to, to get the list of elements to be traversed first, and then traverse the sequence from left to right:

If the current element is None, the current tree is empty otherwise the left subtree of the tree is parsed first, and then the right subtree

type Codec struct {
    l []string
}

func Constructor(a) Codec {
    return Codec{}    
}

func rserialize(root *TreeNode, str string) string {
    if root == nil {
        str += "null,"
    } else {
        str += strconv.Itoa(root.Val) + ","
        str = rserialize(root.Left, str)
        str = rserialize(root.Right, str)
    }
    return str
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    return rserialize(root, "")}// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    l := strings.Split(data, ",")
    for i := 0; i < len(l); i++ {
        ifl[i] ! ="" {
            this.l = append(this.l, l[i])
        }
    }
    return this.rdeserialize()
}

func (this *Codec) rdeserialize(a) *TreeNode {
    if this.l[0] = ="null" {
        this.l = this.l[1:]
        return nil
    }

    val, _ := strconv.Atoi(this.l[0])
    root := &TreeNode{Val: val}
    this.l = this.l[1:]
    root.Left = this.rdeserialize()
    root.Right = this.rdeserialize()
    return root
}





Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️