331. Verify Preorder Serialization of a Binary Tree

leetcode medium

#array#csharp#leetcode#medium#string#tree

Task

Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.

Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.

Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.

Вы можете предположить, что формат ввода всегда действителен.

Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".

Примечание: Вам не разрешено восстанавливать дерево.

Пример:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"

Output: true

C# solution

matched/original

public class Solution {
    public bool IsValidSerialization(string preorder) {
        int slots = 1;
        var nodes = preorder.Split(new char[] { ',' });
        
        foreach (var node in nodes) {
            slots -= 1;
            if (slots < 0) {
                return false;
            }
            if (node != "#") {
                slots += 2;
            }
        }
        
        return slots == 0;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsValidSerialization(string preorder) {
        int slots = 1;
        var nodes = preorder.Split(new char[] { ',' });
        
        foreach (var node in nodes) {
            slots -= 1;
            if (slots < 0) {
                return false;
            }
            if (node != "#") {
                slots += 2;
            }
        }
        
        return slots == 0;
    }
}

Java solution

matched/original

class Solution {
  public boolean isValidSerialization(String preorder) {
    int slots = 1;

    for(String node : preorder.split(",")) {
      --slots;

      if (slots < 0) return false;

      if (!node.equals("#")) slots += 2;
    }

    return slots == 0;
  }
}

JavaScript solution

matched/original

var isValidSerialization = function(preorder) {
    let slots = 1;
    let nodes = preorder.split(',');
    
    for (let node of nodes) {
        slots--;
        if (slots < 0) {
            return false;
        }
        if (node !== "#") {
            slots += 2;
        }
    }
    
    return slots === 0;
};

Python solution

matched/original

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        slots = 1
        nodes = preorder.split(',')
        
        for node in nodes:
            slots -= 1
            if slots < 0:
                return False
            if node != '#':
                slots += 2
        
        return slots == 0

Go solution

matched/original

func isValidSerialization(preorder string) bool {
    slots := 1
    nodes := strings.Split(preorder, ",")
    
    for _, node := range nodes {
        slots--
        if slots < 0 {
            return false
        }
        if node != "#" {
            slots += 2
        }
    }
    
    return slots == 0
}

Explanation

Algorithm

Инициализация и разбор строки:

Инициализируйте переменную slots значением 1, представляющую количество доступных слотов.

Разделите строку по запятым, чтобы получить массив элементов.

Итерация по элементам и проверка:

Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1.

Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию.

Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота.

Проверка завершения:

После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false.

😎