Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to analyze the serialization and deserialization of python binary tree. The content of the article is of high quality, so the editor will share it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Problem description

Serialization is the operation of converting a data structure or object into continuous bits, so that the converted data can be stored in a file or memory, and can also be transferred to another computer environment through the network. the original data can be reconstructed in the opposite way.

Please design an algorithm to serialize and deserialize the binary tree. Instead of limiting the execution logic of your sequence / deserialization algorithm, you just need to ensure that a binary tree can be serialized into a string and deserialize the string into the original tree structure.

Example:

You can put the following binary tree:

one

/\

2 3

/\

4 5

Serialize as "[1, 2, 3, 3, 6, 5]"

BFS solution

This topic said a lot, in fact, is to convert the binary tree into a string, and can also restore the string to the original binary tree.

There are many ways to convert a binary tree into a string, such as preorder traversal, mid-order traversal, subsequent traversal, BFS,DFS can be seen for all kinds of tree traversal, data structure-6, tree. But this question also requires that the string be restored to the original binary tree. The easiest thing to think of is BFS, which traverses one layer at a time.

Take a look at the code.

1public class Codec {

two

3 / / convert the tree to a string (using BFS traversal)

4 public String serialize (TreeNode root) {

5 / / Boundary judgment, return a string "#" if it is empty

6 if (root = = null)

7 return "#"

8 / / create a queue

9 Queue queue = new LinkedList ()

10 StringBuilder res = new StringBuilder ()

11 / / add the root node to the queue

12 queue.add (root)

13 while (! queue.isEmpty ()) {

14 / / the node is out of line

15 TreeNode node = queue.poll ()

16 / / if the node is empty, add a character "#" as the empty node

17 if (node = = null) {

18 res.append ("#,")

19 continue

20}

21 / / if the node is not empty, add the value of the current node to the string

22 / / Note that the nodes are separated by commas, and put the characters below

23 / / the string also restores the binary tree with a comma "," split the string.

24 res.append (node.val + ",")

25 / / the left child node is added to the queue (the left child node may be empty)

26 queue.add (node.left)

27 / / the right child node joins the queue (the right child node may be empty)

28 queue.add (node.right)

29}

30 return res.toString ()

31}

thirty-two

33 / / restore the string to a binary tree

34 public TreeNode deserialize (String data) {

35 / / if it is "#", it means an empty node

36 if (data = "#")

37 return null

38 Queue queue = new LinkedList ()

39 / / because each of the above nodes is separated by a comma, so here

40 / / also split with a comma ","

41 String [] values = data.split (",")

42 / / the above uses BFS, so the first value is the value of the root node, where the root node is created

43 TreeNode root = new TreeNode (Integer.parseInt (values [0]))

44 queue.add (root)

45 for (int I = 1; I < values.length; iTunes +) {

46 / / the nodes in the queue are out of stack.

47 TreeNode parent = queue.poll ()

48 / / because the left and right child nodes appear in pairs in BFS, the two values next to each other are

49 / / the value of the left child node is the value of the right child node, and the current value represents the child node if the current value is "#"

50 / / is empty. If it is not "#", it means it is not empty.

51 if (! "#" .equals (values [I])) {

52 TreeNode left = new TreeNode (Integer.parseInt (values [I]))

53 parent.left = left

54 queue.add (left)

55}

56 / / the above is the value of the left child node if it is not empty. Here is the value of the right child node. Notice that there is an inode +

57 if (! "#" .equals (values [+ + I]) {

58 TreeNode right = new TreeNode (Integer.parseInt (values [I]))

59 parent.right = right

60 queue.add (right)

61}

62}

63 return root

64}

65}

DFS solution

DFS traversal starts from the root node, goes straight to the left child node, returns to the parent node when it reaches the leaf node, and then continues traversing from the right child node of the parent node.

1class Codec {

two

3 / / convert the tree to a string (using DFS traversal, also preorder traversal, in the following order: root node → left subtree → right subtree)

4 public String serialize (TreeNode root) {

5 / / Boundary judgment, return a string "#" if it is empty

6 if (root = = null)

7 return "#"

8 return root.val + "," + serialize (root.left) + "," + serialize (root.right)

9}

ten

11 / / restore the string to a binary tree

12 public TreeNode deserialize (String data) {

13 / / split the string data with a comma "," and store it in the queue

14 Queue queue = new LinkedList (Arrays.asList (data.split (","))

15 return helper (queue)

16}

seventeen

18 private TreeNode helper (Queue queue) {

19 / / out of the team

20 String sVal = queue.poll ()

21 / / if "#" indicates an empty node

22 if ("#" .equals (sVal))

23 return null

24 / / otherwise create the current node

25 TreeNode root = new TreeNode (Integer.valueOf (sVal))

26 / / create the left and right subtrees, respectively

27 root.left = helper (queue)

28 root.right = helper (queue)

29 return root

30}

31}

It is very simple to convert a binary tree into a string. The key is how to restore the converted string to the original binary tree. Here, it is easy to use BFS and DFS.

On how to analyze the serialization and deserialization of python binary tree is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.