Verify Preorder Serialization of a Binary Tree

本文主要是介绍Verify Preorder Serialization of a Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考：点击打开链接

对于二叉树，我们把空的地方也作为叶子节点（如题目中的#），那么有

• 所有的非空节点提供2个出度和1个入度（根除外）
• 所有的空节点但提供0个出度和1个入度

我们在遍历的时候，计算diff = outdegree – indegree. 当一个节点出现的时候，diff – 1，因为它提供一个入度；当节点不是#的时候，diff+2(提供两个出度) 如果序列式合法的，那么遍历过程中diff >=0 且最后结果为0.

public class Solution {public boolean isValidSerialization(String preorder) {String[] strs = preorder.split(",");int diff = 1;for (String str: strs) {if (--diff < 0) {return false;}if (!str.equals("#")) {diff = diff + 2;}}return diff == 0;}
}

这篇关于Verify Preorder Serialization of a Binary Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---