参考代码下载地址 https://static.nowcoder.com/b/nowcoder_ds.zip
有任何理解问题请联系QQ 77963306
或者邮件 yexiangyu@nowcoder.com

TreeNode

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

TreeNode是经典的二叉树节点,在数据的序列化和反序列按照层遍历来处理的。
TreeNode
以上二叉树会被序列化为 {1,2,3,#,#,4,#,#,5}
1:root节点1,是第一层
2,3:然后第二层是2,3
#,#,4,#:第三层分别是2节点的两个孩子节点空,用#来表示,然后3节点的左孩子为4,右孩子节点为#
#,5:第四层4节点的左孩子是空,右孩子为5
最后一层5节点的两个空孩子不便利

把一棵树保存为测试数据文本代码请参考压缩包 https://static.nowcoder.com/b/nowcoder_ds.zip

ListNode

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};


单链表结构,格式{0,1,2,3,4},每个链表节点一个数字,从头到尾排布,通过,分开。

TreeLinkNode

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :
            val(x), left(NULL), right(NULL), next(NULL) {
    }
};

在TreeNode的基础上,额外横向增加一个链接节点,数据的序列化格式在TreeNode的基础上,额外增加next节点的数据,图中红色链路为next
图片说明
上图中2节点的next为3节点,以上链接二叉树会被序列化为 {[1,2,3,#,#,4,#,#,5],[#,3,#,#,#]}

注意这个数据结构中,所有的节点val必须不同,否则OJ在解析数据的时候后半段的link数据就无法定位准确的节点

把一个链接二叉树保存为测试数据文本代码请参考压缩包 https://static.nowcoder.com/b/nowcoder_ds.zip

RandomListNode

struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};

在ListNode基础上,额外增加一个random的链接节点,数据的序列化格式在ListNode的基础上,额外增加random节点的数据,图中红色链路为random

上图对应测试数据为 {-1,8,7,-3,4,4,-3,#,#,8},前五个数字是链表节点,后五个数字表示各个节点的random的链接点

注意这个数据结构中,所有的节点label必须不同,否则OJ在解析数据的时候后半段的random数据就无法定位准确的节点

把一个随机链表保存为测试数据文本代码请参考压缩包 https://static.nowcoder.com/b/nowcoder_ds.zip

UndirectedGraphNode

struct UndirectedGraphNode {
    int label;
    vector<struct UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) :
            label(x) {
    }
};

无向图里每个节点都有一个 唯一的数字ID ,每个节点的序列化通过[]保存,每个节点第一个元素后跟随的是这个节点连接的其他节点,所有节点根据label从小到大输出,以下图
图片说明
上图中注意2节点还链接到自己节点,上图对应测试数据为{[0,1,2],[1,2],[2,2]},从小到大0,1,2三个节点

注意这个数据结构中,所有的节点label必须不同,否则OJ在解析数据节点后半段的连接点就无法定位准确的节点

把一个无向图保存为测试数据文本代码请参考压缩包 https://static.nowcoder.com/b/nowcoder_ds.zip