题目描述

一种把二叉树序列化的方式是使用前序遍历。当我们遇到非空节点时，直接记录它的值；当我们遇到空节点时，记录#。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上述二叉树可以被序列化成"9,3,4,#,#,1,#,#,2,#,6,#,#"，#表示空节点。

给定一个用逗号隔开的序列，请判断它是不是一个合法的二叉树前序遍历。请不要将二叉树重建出来。

被逗号隔开的值要么是整数，要么是#。

给定的序列一定是合法的。例如，不会出现两个连续逗号的情况：1,,3。

样例1

输入："9,3,4,#,#,1,#,#,2,#,6,#,#"
输出：true

样例2

输入："1,#"
输出：false

样例3

输入："9,#,#,1"
输出：false

算法

(二叉树遍历) $O(n)$

一般来说，只给出前序遍历，并不能唯一确定一棵二叉树。但这道题目中还给出了所有空节点的位置，所以可以唯一确定一棵二叉树。

我们用先根顺序递归遍历整棵树，遍历时用一个指针在给定数组中指向当前节点的值，如果遇到#，则说明遇到了空节点，直接return；如果遇到整数，说明遍历到了树中的一个节点，我们先将指针后移，表示先输出根节点，然后依次递归遍历左子树和右子树。
如果递归还没结束但数组已经遍历完，或者递归结束但数组还没遍历完，则说明给定的序列不是一个合法的前序遍历。

时间复杂度分析：递归遍历时只将数组扫描了一遍，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    bool ans = true;
    bool isValidSerialization(string preorder) {
        preorder += ',';
        int u = 0;
        dfs(preorder, u);
        return ans && u == preorder.size();
    }

    void dfs(string &preorder, int &u)
    {
        if (u == preorder.size())
        {
            ans = false;
            return;
        }
        if (preorder[u] == '#')
        {
            u += 2;
            return;
        }
        while (preorder[u] != ',') u ++ ; u ++ ;
        dfs(preorder, u);
        dfs(preorder, u);
    }
};