程式隨筆
0%

【LeetCode】Serialize and Deserialize BST

Posted on Edited on In Disqus:

#題目

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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public string serialize(TreeNode root) {
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data) {
        
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

#解題

serialize

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod()]
public void serializeTest()
{
    //arrange
    var node = new TreeNode(1);
    var sut = new Codec();

    var expected = "1!#!#!";

    //act
    var actual = sut.serialize(node);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Codec
{
    public string serialize(TreeNode root)
    {
        string res = root.val + "!";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        return null;
    }
}

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[TestMethod()]
public void serializeTest_傳入Null應回傳空字串()
{
    //arrange
    var sut = new Codec();
    
    var expected = "#!";

    //act
    var actual = sut.serialize(null);

    //assert
    actual.Should().Be(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Codec
{
    public string serialize(TreeNode root)
    {
        if (root == null)
        {
            return "#!";
        }

        string res = root.val + "!";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        return null;
    }
}

案例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod()]
public void serializeTest_有左邊子節點()
{
    //arrange
    var node = new TreeNode(1);
    node.left = new TreeNode(2);

    var sut = new Codec();

    var expected = "1!2!#!#!#!";

    //act
    var actual = sut.serialize(node);

    //assert
    actual.Should().BeEquivalentTo(expected);
}

測試直接通過

案例四

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[TestMethod()]
public void serializeTest_有右邊子節點()
{
    //arrange
    var node = new TreeNode(1);
    node.right = new TreeNode(2);

    var sut = new Codec();

    var expected = @"1!#!2!#!#!";

    //act
    var actual = sut.serialize(node);

    //assert
    actual.Should().BeEquivalentTo(expected);
}

測試直接通過

案例五

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[TestMethod()]
public void serializeTest_三層節點()
{
    //arrange
    var node = new TreeNode(1);
    node.left = new TreeNode(2);
    node.right = new TreeNode(3);

    node.left.left = new TreeNode(4);
    node.right.right = new TreeNode(5);

    var sut = new Codec();

    var expected = "1!2!4!#!#!#!3!#!5!#!#!";

    //act
    var actual = sut.serialize(node);

    //assert
    actual.Should().BeEquivalentTo(expected);
}

圖解

/images/20180609/1.gif

deserialize

案例一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
[TestMethod()]
public void deserializeTest()
{
    //arrange
    var nodeSerializeString = @"1!#!#!";
    var sut = new Codec();
           
    var expected = new TreeNode(1);
    //act
    var actual = sut.deserialize(nodeSerializeString);

    //assert
    actual.Should().BeEquivalentTo(expected);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Codec
{
    public string serialize(TreeNode root)
    {
        if (root == null)
        {
            return "#!";
        }

        string res = root.val + "!";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(string data)
    {
        var nodeData = data.Split(new string[] { "!" }, StringSplitOptions.RemoveEmptyEntries);

        var queue = new Queue<string>();

        foreach (var node in nodeData)
        {
            queue.Enqueue(node);
        }

        return RebuildNode(queue);
    }

    private TreeNode RebuildNode(Queue<string> queue)
    {
        var Value = queue.Dequeue();

        if (Value == "#")
        {
            return null;
        }

        TreeNode node = new TreeNode(int.Parse(Value));

        node.left = RebuildNode(queue);
        node.right = RebuildNode(queue);

        return node;
    }
}

Queue類別為先進先出**(FIFO)，與Stack**後進先出(LIFO)使用方法相反

MSDN - Queue 類別

案例二

1
2
3
4
5
6
7
8
9
10
11
12
13
[TestMethod()]
public void deserializeTest_Null_Node()
{
    //arrange
    var nodeSerializeString = "#!";
    var sut = new Codec();

    //act
    var actual = sut.deserialize(nodeSerializeString);

    //assert
    actual.Should().BeNull();
}

直接通過測試

案例三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod()]
public void deserializeTest_有左邊子節點()
{
    //arrange
    var nodeSerializeString = @"1!4!#!#!#!";
    var sut = new Codec();

    var expected = new TreeNode(1);
    expected.left = new TreeNode(4);
    //act
    var actual = sut.deserialize(nodeSerializeString);

    //assert
    actual.Should().BeEquivalentTo(expected);
}

直接通過測試

案例四

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[TestMethod()]
public void deserializeTest_有右邊子節點()
{
    //arrange
    var nodeSerializeString = @"1!#!2!#!#!";
    var sut = new Codec();

    var expected = new TreeNode(1);
    expected.right = new TreeNode(2);
    //act
    var actual = sut.deserialize(nodeSerializeString);

    //assert
    actual.Should().BeEquivalentTo(expected);
}

直接通過測試

案例五

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[TestMethod()]
public void deserializeTest_三層節點()
{
    //arrange
    var nodeSerializeString = @"1!2!4!#!#!#!3!#!5!#!#!";
    var sut = new Codec();


    var expected = new TreeNode(1);
    expected.left = new TreeNode(2);
    expected.right = new TreeNode(3);

    expected.left.left = new TreeNode(4);
    expected.right.right = new TreeNode(5);

    //act
    var actual = sut.deserialize(nodeSerializeString);

    //assert
    actual.Should().BeEquivalentTo(expected);
}

直接通過測試

#解析

/images/20180609/2.jpg

這題一樣是參考了別人的答案然後去理解，一開始搞得很複雜，想說回傳Json然後再去解析，忽略了二元樹遍歷規則，果然還要多練練才行。