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

旧城等待， 2022-10-08 00:48 150阅读 0赞

> 序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 \#。![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]
> 
> 示例 1:
> 
> 输入: "9,3,4,\#,\#,1,\#,\#,2,\#,6,\#,\#"  
> 输出: true  
> 示例 2:
> 
> 输入: "1,\#"  
> 输出: false

>     class Solution {
>         public boolean isValidSerialization(String preorder) {
>             /**
>             二叉树特点:  叶子结点=非叶子节点+1
>             在最后一个位置之前的每一个位置  叶子结点 的数量<=非叶子节点的数量
>              */
>              int YZ=0;//叶子
>              int FYZ=0;//非叶子
>              for(int i=0;i<preorder.length();i++){
>                  char c=preorder.charAt(i);
>                 
>                  if(c=='#'){
>                      YZ++;
>                  }else if(c!=','){
>                      //说明是非叶子
>                      FYZ++;
>                      //有可能是92 那么 先9  后2 是一个
>                      //所以得往后移动
>                      while(i<preorder.length()&&Character.isDigit(preorder.charAt(i))){
>                          i++;
>                      }
>                      //s.charAt(i)不是一个数了 退出
>                      i--;//退一个 回到数的末尾
>                  }
>     
>                  if(i<preorder.length()-1&&YZ>FYZ) return false;
>              }
>              return (YZ==FYZ+1)?true:false;
>         }
>     }
> 
>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/4f7755915fd240e7b8a60b5314b58d46.png