verify-preorder-serialization-of-a-binary-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node&#39;s value. If it is a null node, we record using a sentinel value such as <code>&#39;#&#39;</code>.
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/12/pre-tree.jpg" style="width: 362px; height: 293px;" />
For example, the above binary tree can be serialized to the string <code>&quot;9,3,4,#,#,1,#,#,2,#,6,#,#&quot;</code>, where <code>&#39;#&#39;</code> represents a null node.

Given a string of comma-separated values <code>preorder</code>, return <code>true</code> if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character <code>&#39;#&#39;</code> representing null pointer.

You may assume that the input format is always valid.

<ul>
	<li>For example, it could never contain two consecutive commas, such as <code>&quot;1,,3&quot;</code>.</li>
</ul>

Note:&nbsp;You are not allowed to reconstruct the tree.

&nbsp;
Example 1:
<pre>Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
</pre>Example 2:
<pre>Input: preorder = "1,#"
Output: false
</pre>Example 3:
<pre>Input: preorder = "9,#,#,1"
Output: false
</pre>
&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= preorder.length &lt;= 104</code></li>
	<li><code>preorder</code> consist of integers in the range <code>[0, 100]</code> and <code>&#39;#&#39;</code> separated by commas <code>&#39;,&#39;</code>.</li>
</ul>