Line data    Source code

       1              : // Copyright (c) 2022 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : // Created: 2022/01/17 14:50
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include <string>
      21              : 
      22              : namespace {
      23              : class Solution {
      24              : public:
      25            4 :     bool isValidSerialization(const std::string& preorder) {
      26            4 :         if (preorder == "#")
      27            0 :             return false;
      28            4 :         int len = preorder.length(), inDegree = 0, outDegree = 0;
      29           45 :         for (int i = 0; i < len; ++i) {
      30           42 :             if (preorder[i] == ',')
      31           19 :                 continue;
      32           23 :             if (i == 0) {
      33            4 :                 if (preorder[i] == '#')
      34            0 :                     return false;
      35            4 :                 outDegree += 2;
      36              :             } else {
      37           19 :                 if (preorder[i] != '#') {
      38            6 :                     outDegree += 2;
      39              :                 }
      40           19 :                 inDegree++;
      41              :             }
      42           23 :             if (i != len - 1 && inDegree >= outDegree) {
      43            1 :                 return false;
      44              :             }
      45           26 :             while ((i + 1 < len && preorder[i + 1] != ',') || (i + 1 == len)) {
      46            4 :                 i++;
      47              :             }
      48              :         }
      49            3 :         return inDegree == outDegree;
      50              :     }
      51              : };
      52              : } // namespace
      53              : 
      54            4 : TEST(Leetcode, verify_preorder_serialization_of_a_binary_tree) {
      55            1 :     Solution s;
      56              : 
      57            1 :     EXPECT_TRUE(s.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));
      58            1 :     EXPECT_TRUE(s.isValidSerialization("9,#,92,#,#"));
      59            1 :     EXPECT_FALSE(s.isValidSerialization("1,#"));
      60            1 :     EXPECT_FALSE(s.isValidSerialization("9,#,#,1"));
      61            1 : }