<p>One way to serialize a binary tree is to use <strong>preorder traversal</strong>. 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>.</p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/12/pre-tree.jpg" style="width: 362px; height: 293px;" />
<p>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.</p>

<p>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.</p>

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

<p>You may assume that the input format is always valid.</p>

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

<p><strong>Note:&nbsp;</strong>You are not allowed to reconstruct the tree.</p>

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

<ul>
	<li><code>1 &lt;= preorder.length &lt;= 10<sup>4</sup></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>

#define LL long long
#define PQ priority_queue
#define VI vector<int>
#define VL vector<long>
#define VUL vector<unsigned long>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VVL vector<vector<long>>
#define VVUL vector<vector<unsigned long>>
#define VVB vector<vector<bool>>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VS vector<string>
#define VSEI vector<set<int>>
#define VVS vector<vector<string>>
#define PII pair<int, int>
#define PLL pair<long, long>
#define PLI pair<long, int>
#define VPII vector<pair<int, int>>
#define VPLL vector<pair<long, long>>
#define VVPII vector<vector<pair<int, int>>>
#define VVPLL vector<vector<pair<long, long>>>
#define VVPLI vector<vector<pair<long, int>>>
#define UMII unordered_map<int, int>
#define UMSS unordered_map<string, string>
#define UMCS unordered_map<char, string>
#define UM unordered_map
#define USI unordered_set<int>
#define USS unordered_set<string>
#define QPII queue<pair<int, int>>

#define DSZ(g, M, N) const int M = g.size(), N = g[0].size()
#define D4(dx, dy)             \
    int dx[4] = {-1, 1, 0, 0}; \
    int dy[4] = {0, 0, -1, 1}
#define D8(dx, dy)                           \
    int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; \
    int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}
#define OB(x, y, M, N) ((x) >= (M) || (y) >= (N) || (x) < 0 || (y) < 0)
using AI3 = std::array<int, 3>;
using VAI3 = std::vector<std::array<int, 3>>;
using AI4 = std::array<int, 4>;
using VAI4 = std::vector<std::array<int, 4>>;

#define G_DSZ(g, M, N) const int M = g.size(), N = g[0].size()
#define G_D4D(d) vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
#define G_D8D(d) vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}
#define G_SZ(g, M, N) M = g.size(), N = g[0].size()
#define G_OB(x, y, M, N) ((x) >= (M) || (y) >= (N) || (x) < 0 || (y) < 0)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)

class Solution {
public:
    bool isValidSerialization(string preorder) {
        string temp;
        vector<string> tokens;
        for (auto c : preorder) {
            if (c == ',') {
                tokens.push_back(temp);
                temp.clear();
            } else {
                temp.push_back(c);
            }
        }
        tokens.push_back(temp);
        int cursor = 0;
        return dfs(tokens, cursor) && cursor == tokens.size();
    }

private:
    bool dfs(VS &tokens, int &cursor) {
        if (cursor >= tokens.size()) {
            return false;
        }
        string cur = tokens[cursor];
        cursor++;
        if (cur == "#") {
            return true;
        } else {
            return dfs(tokens, cursor) && dfs(tokens, cursor);
        }
    }
};

13300