LeetCode331. 验证二叉树的前序序列化

超、凢脫俗 2022-11-07 13:22 109阅读 0赞

难度：`中等`  
题目描述：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]

> 例如，上面的二叉树可以被序列化为字符串 “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  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution { 
    public:
        int n;
        bool isValidSerialization(string preorder) { 
            n = preorder.size();
            int cnt = 0;
            int num = 0;
            for(int i=0; i<n; i++) { 
                if(isdigit(preorder[i])) { 
                    num = 1;
                }
                else if(preorder[i] == ',') { 
                    cnt += num;
                    if(cnt < 0 && i != n-1)
                        return false;
                }
                else if(preorder[i] == '#') { 
                    num = -1;
                }
            }
            return cnt+num == -1;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221023/2227037890f843b4b29464acc3179df6.png