我们以BFS
顺序表示二叉树。
例如:
BFS 顺序或上面的二叉树为[1,2,3]
,因此该树将被序列化为{1,2,3}
。
对于:
两棵树的 BFS 顺序相同都为:[1,2]。为了区分它们,我们使用{1,2,#}
代表第一个,{1,#,2}
代表第二个。 #代表空节点。对于{1,2,#},我们可以通过忽略{1,2}
尾部的空节点来使其更短。
让我们来看一个更大的二叉树:
它将被序列化为{1,2,3,4,5,#,6,#,#,7,8}
。
1:根
2:1的左子树
3:1的右子树
4:2的左子树
5:2的右子树
#:3的左子树
6:3的右子树
#:4的左子树
#:4的右子树
7:5的左子树
8:5的右子树
因为6、7、8位于bfs顺序的末尾,它们的左子树和右子树都为空,所以可以忽略。