Leetcode - Find Median from Data Stream
Leetcode - Validate IP Address

Leetcode - Serialize and Deserialize Binary Tree

violet posted @ Jun 16, 2020 08:25:30 AM in 算法 with tags Algorithm BFS Golang tree , 464 阅读

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

 

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
}

func Constructor() Codec {
    return Codec {
    } 
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return "[]"
    }
    strs := []string{}
    queue := []*TreeNode{root}
    strs = append(strs, strconv.Itoa(root.Val))
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node.Left != nil {
            queue = append(queue, node.Left)
            strs = append(strs, strconv.Itoa(node.Left.Val))
        } else {
            strs = append(strs, "null")
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
            strs = append(strs, strconv.Itoa(node.Right.Val))
        } else {
            strs = append(strs, "null")
        }
    }
    i := len(strs)-1
    for i >= 0 && strs[i] == "null" {
        i--
    }

    return "[" + strings.Join(strs[0:i+1], ",") + "]"
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    if data == "[]" {
        return nil
    }
    strs := strings.Split(data[1:len(data)-1], ",")
    // [1, 2, 3, null, null, 4, 5]
    
    val, _ := strconv.Atoi(strs[0])
    root := &TreeNode{Val: val}
    queue := []*TreeNode{root}
    i := 1
    
    for len(queue) > 0 {
        size := len(queue)
        for j := 0; j < size && i < len(strs); j++ {
            if strs[i] == "null" {
                queue[j].Left = nil
            } else {
                val, _ := strconv.Atoi(strs[i])
                queue[j].Left = &TreeNode{Val: val}
                queue = append(queue, queue[j].Left)
            }
            i++
            if i >= len(strs) {
                break
            }
            if strs[i] == "null" {
                queue[j].Right = nil
            } else {
                val, _ := strconv.Atoi(strs[i])
                queue[j].Right = &TreeNode{Val: val}
                queue = append(queue, queue[j].Right)
            }
            i++
        }
        queue = queue[size:]
    }
    return root
}


/**
 * Your Codec object will be instantiated and called as such:
 * obj := Constructor();
 * data := obj.serialize(root);
 * ans := obj.deserialize(data);
 */
Delhi Escorts 说:
Jul 17, 2021 11:22:50 PM

It is one of the best topic that I have read.

Bhawna 说:
Feb 14, 2022 03:26:48 PM

violet's Blog is a wonderful and amazing blog for readers. [url=https://www.ishadelhi.in]Hot Delhi Escorts[/url]

Bhawna 说:
Feb 14, 2022 03:30:49 PM
Your content is incredible substances on this site. Extraordinary work. Call Girls in Delhi Delhi Escorts Delhi Escorts Service Escorts in Delhi Delhi Call Girls

 

 
11th Exam Pattern 20 说:
Feb 17, 2023 12:29:39 AM

Students are studying well for the Main Exam 2024, and we urge that all students use specific 11th Exam Pattern 2024 and 11th 2024 Exam Patterns. Putting these into practice can help you answer more questions. Download the 11th Blueprint 2024 XI Exams 2024 Exam Pattern Set-Wisdom Hindi is divided into subjects. 11th Exam Pattern 2024 Sanskrit in English History Geography Economics and Politics Sociology Anatomy Home of Science HYGIENE AND PHYSIOLOGY Physics, Chemistry, and Biology Maintain a book for business studies.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter