See all code: Click to see all code

Deserialization of binary trees

introduce

Tree deserialization means that a binary tree is regenerated from a serialized string or other form of data. This binary tree is the result of serialized string [5,4,null,null,3,2,1], and now the string is regenerated into a binary tree. This is where the string is serialized.

Their thinking

  • First, you should get a serialized piece of data, which could be a queue, stack, string (split with characters in the middle), or some other form of data
  • When there is no data underneath a node, I use thenullFor example, there is no data below node 2, which is used in a stringnullTo represent the
  • Here I convert the string to queue form, of course it is possible to use string form, for example: passsplitMethod to split into arrays
  • Create a queue and put the nodes you want to process into the queue. For example, put the left and right branches into the queue every time you loop, because the queue hasFIFOAfter processing the left branch, it can be released to the right branch node
  • Next, analyze the code

code

TreeNode structure

type TreeNode struct {
	val   string
	left  *TreeNode
	right *TreeNode
}
Copy the code

Val is the data of the current node; Left and right store the data of left branch and right branch respectively

Generate the corresponding TreeNode for each data

func GenerateNode(str string) *TreeNode {
	if str == "null" {
		return nil
	}
	return &TreeNode{val: str}
}
Copy the code

This method is used to generate a TreeNode object. If the node has no children, it will return a null pointer. If the parameter is not null, it will return a created TreeNode object and assign a value to val

Deserialization method

func DeserializationTb(dataQueue []string) (resultNode *TreeNode) {
	if len(dataQueue) == 0 {
		return nil
	}
	var tempNodeQueue []*TreeNode
	resultNode = generateNode(dataQueue[len(dataQueue) - 1])
	dataQueue = dataQueue[:len(dataQueue) - 1]
	ifresultNode ! =nil {
		tempNodeQueue = append(tempNodeQueue,resultNode)
	}
	var tempNode *TreeNode
	for len(tempNodeQueue) ! =0 {
		tempNode = tempNodeQueue[0]
		tempNodeQueue = tempNodeQueue[1:]
		if len(dataQueue) > 0 {
			tempNode.left = generateNode(dataQueue[len(dataQueue) - 1])
			dataQueue = dataQueue[:len(dataQueue) - 1]
			tempNode.right = generateNode(dataQueue[len(dataQueue) - 1])
			dataQueue = dataQueue[:len(dataQueue) - 1]}iftempNode.left ! =nil {
			tempNodeQueue = append(tempNodeQueue,tempNode.left)
		}
		iftempNode.right ! =nil {
			tempNodeQueue = append(tempNodeQueue,tempNode.right)
		}
	}
	return
}
Copy the code

Code reading

This method is more code, here will block to say:

if len(dataQueue) == 0 {
		return nil
}
Copy the code

This line of code is nothing more than a boundary condition judgment problem, when the incoming queue has no data will return a null, why queue? Because I’ve converted strings into queues

var tempNodeQueue []*TreeNode
resultNode = generateNode(dataQueue[len(dataQueue) - 1])
dataQueue = dataQueue[:len(dataQueue) - 1]
ifresultNode ! =nil {
	tempNodeQueue = append(tempNodeQueue,resultNode)
}
Copy the code

var tempNodeQueue [] * TreeNode: here are the reasons why create a TreeNode pointer array data storage nodes to operate, because I will be serialized data into the queue, so in the last element in the array should be the first array, the first out of the same data is the root node of the binary tree, to save this node to the queue Then the queue will be used in the for loop below, and the rest will come next.

ResultNode = generateNode(dataQueue[len(dataQueue) -1]): The TreeNode object is generated by generateNode

DataQueue = dataQueue[:len(dataQueue) -1]: Because an array is out of the queue, it should be removed

TempNodeQueue = append(tempNodeQueue,resultNode): After a nullity process, this node is saved to the queue mentioned above

for len(tempNodeQueue) ! =0 {
    tempNode = tempNodeQueue[0]
    tempNodeQueue = tempNodeQueue[1:]
    if len(dataQueue) > 0 {
        tempNode.left = generateNode(dataQueue[len(dataQueue) - 1])
        dataQueue = dataQueue[:len(dataQueue) - 1]
        tempNode.right = generateNode(dataQueue[len(dataQueue) - 1])
        dataQueue = dataQueue[:len(dataQueue) - 1]}iftempNode.left ! =nil {
        tempNodeQueue = append(tempNodeQueue,tempNode.left)
    }
    iftempNode.right ! =nil {
        tempNodeQueue = append(tempNodeQueue,tempNode.right)
    }
}
Copy the code

After entering the For loop, the queue has data in it. If you have data in it, you can perform the following operations:

TempNodeQueue = tempNodeQueue[1:]: Because the previous line ejected data from the queue, the line removes the ejected data

DataQueue [len(dataQueue) -1] = generateNode(dataQueue[len(dataQueue) -1]) The right branch assigns values. The next line of code removes the popup data, and the next two lines do the same for the right node as for the left

TempNodeQueue = append (tempNodeQueue, tempNode. Left) : if tempNode nodes exist when they left, save it to the queue traversal tempNodeQueue queue, to perform the above steps again.

May some partners have questions?

The returned resultNode variable is assigned only once. How is the child node assigned? Because ALL TreeNode nodes ARE handled by Pointers,

The first line of code in the For popup points to the address of the resultNode, so after generating the tree, I just need to grab the root node of the tree

Serialization of binary trees

introduce

What about tree serialization? I can convert this tree into a data structure of a certain format, such as a piece of text that can be persisted to hard disk.

What does that do? For example, the data in Redis is stored in memory, and it has a function to save the data to the hard disk at regular intervals to prevent sudden power outages and data loss

I want to serialize the data in a binary tree to disk so that the next time I use the data in the binary tree, I can generate the tree directly

Their thinking

  • The idea is to solve this problem by iterating through the layers of a binary tree, and treating a node as empty when it has no children, which I’m using herenullTo represent the
  • In this case I’m serializing the left child first, and then the right child
  • As with deserialization, I used a queue structure for the temporary data, and also needed to store the obtained data in a queue
  • At the beginning of the program, if the given head node is not empty, the head node is added to the queue
  • When traversing the queue, eject the data in the queue (note: queue has FIFO features), and put the val of this node into the queue to save the data
  • Put the left and right children of the node in the queue and repeat the above steps

code

/** serialize binary tree */
func SerializationTb(bt *TreeNode) (saveSerData []string) {
	root := bt
	var tempQueue []*TreeNode
	ifroot ! =nil {
		tempQueue = append(tempQueue, root)
	}
	var tempNode *TreeNode
	for len(tempQueue) ! =0 {
		tempNode = tempQueue[0]
		iftempNode ! =nil {
			saveSerData = append(saveSerData, tempNode.val)
		} else {
			saveSerData = append(saveSerData, "null")
		}
		tempQueue = tempQueue[1:]
		iftempNode ! =nil {
			tempQueue = append(tempQueue, tempNode.left)
			tempQueue = append(tempQueue, tempNode.right)
		}
	}
	return
}
Copy the code

Code reading

These code is still very nice to understand, here is a for inside the code ~~

TempNode = tempQueue[0]: Pops a data in the queue

SaveSerData = append(saveSerData, tempNode.val): Saves the val attribute of tempNode to the saveSerData queue

If a node has no children, then null is used. If a node has no children, then null is added to the queue. Okay

TempQueue = tempQueue[1:]: Reassign to queue, remove the popup data

TempQueue = append(tempQueue, tempNode.left): add the left node to the queue, as in the next line

The results