Skip to content

Latest commit

 

History

History
 
 

331.Verify-Preorder-Serialization-of-a-Binary-Tree

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

331.Verify-Preorder-Serialization-of-a-Binary-Tree

此题用到了这么一个性质:对于满二叉树,所有节点的入度和出度之差为0.

关于入度和出度,我们知道,根节点的净值是-2(两个出度),非叶子节点的净值是-1(一个入度两个出度),叶子节点的净值是1(一个入度零个出度)。在对先序遍历的过程中,我们只能区分叶子和非叶子节点,但是无法再细分是否是根节点。不过因为根节点只有一个,所以我们如果把根节点也当做一般的非叶子节点来处理的话,遍历所有节点之后的总净值应该是1。也就是说,如果我们按先序遍历所有节点,遇到非#节点就减一,遇到#节点就加一,最终的结果必须是1。

此外还有另外一个判定条件。在先序遍历的过程中,总有一些子二叉树是没有被完全遍历完的,也就是说,对于这些子二叉树,已经遍历的非叶子节点总比已经遍历的叶子节点多。所以按照上述的规则,遍历的过程中(不包括最后一个节点),总净值不能大于0。注意,一旦把最后一个节点遍历完毕,根据上一个结论,总净值必须是1。

Leetcode Link