本文共 1164 字，大约阅读时间需要 3 分钟。

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. 解题

类似题目：

• 空节点 总比 有效节点 多一个
• 初始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

转载地址：https://michael.blog.csdn.net/article/details/105679759 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！