LeetCode 331. 验证二叉树的前序序列化Michael是个半路程序员-

1. 题目

序列化二叉树的一种方法是使用前序遍历。
当我们遇到一个非空节点时，我们可以记录下这个节点的值。
如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

     _9_     /       3 2 /    /   4 1  #  6 /  /    /  # # # #   # # 

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。
编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。

你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。 示例 1: 输入: "9,3,4,#,#,1,#,#,2,#,6,#,#" 输出: true  示例 2: 输入: "1,#" 输出: false  示例 3: 输入: "9,#,#,1" 输出: false 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：LeetCode 297. 二叉树的序列化与反序列化（前序遍历&层序遍历）

• 空节点 总比 有效节点 多一个
• 初始degree为1，遇到数字+1，遇到# -1
• 过程当中degree不得等于零，等于零相当于结束了
• 必须在结束的时候等于0

class Solution { public: bool isValidSerialization(string preorder) { if(preorder[0]=='#') return preorder.size()==1;//根节点为空 int degree = 1, i, n = preorder.size(); for(i = 0; i < n-1; ++i) { if(i==0 || (preorder[i]==','&& isdigit(preorder[i+1])))        degree++;//数字 else if(preorder[i] == ',' && preorder[i+1]=='#')        degree--;//空节点 if(degree==0 && i != n-2) return false;//过程中等于0，不行 } return degree==0; } }; 

4 ms 6.8 MB