牛客编程题高级数据结构格式说明

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

TreeNode

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

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三个节点