Description Link to heading

331. Verify Preorder Serialization of a Binary Tree (Medium)

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as '#'.

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

Given a string of comma-separated values preorder, return true 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 '#' representing null pointer.

You may assume that the input format is always valid.

  • For example, it could never contain two consecutive commas, such as "1,,3".

Note: You are not allowed to reconstruct the tree.

Example 1:

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

Example 2:

Input: preorder = "1,#"
Output: false

Example 3:

Input: preorder = "9,#,#,1"
Output: false

Constraints:

  • 1 <= preorder.length <= 10⁴
  • preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

Solution Link to heading

Reduction Link to heading

Essentially, this approach remains rooted in recursive thinking. During the pre-order traversal, it is noticeable that each leaf node is invariably followed by two null nodes. Therefore, we can reverse this process by reducing a continuous sequence of one non-empty node and two empty nodes into a single empty node. This process somewhat resembles a match-three game and can be implemented using a stack. In the end, we can determine whether there is only one remaining empty node in the stack to make the final judgment.

Recursion Link to heading

The recursive approach draws inspiration from 剑指 Offer 37. 序列化二叉树 (Hard). However, the key difference lies in the fact that we only need to determine whether the left subtree and right subtree meet the requirements, without the necessity of returning their root nodes.

Code Link to heading

Reduction Link to heading 

class Solution {
  public:
    void string2vec(string &preorder, vector<string> &strs) {
        for (int i = 0; i < preorder.size(); ++i) {
            int r = i;
            while (r < preorder.size() && preorder[r] != ',') {
                ++r;
            }
            strs.push_back(preorder.substr(i, r - i));
            i = r;
        }
    }
    bool isValidSerialization(string preorder) {
        vector<string> strs;
        string2vec(preorder, strs);
        int n = strs.size();
        stack<string> stk;
        for (int i = 0; i < n; ++i) {
            if (strs[i] != "#") {
                stk.push(strs[i]);
            } else {
                while (stk.size() >= 2 && stk.top() == "#") {
                    stk.pop();
                    if (stk.top() == "#") {
                        return false;
                    }
                    stk.pop();
                }
                stk.push("#");
            }
        }
        return stk.size() == 1 && stk.top() == "#";
    }
};

Recursion Link to heading 

class Solution {
  public:
    void string2vec(string &preorder, vector<string> &strs) {
        for (int i = 0; i < preorder.size(); ++i) {
            int r = i;
            while (r < preorder.size() && preorder[r] != ',') {
                ++r;
            }
            strs.push_back(preorder.substr(i, r - i));
            i = r;
        }
    }
    bool dfs(vector<string> &strs, int &idx) {
        if (idx >= strs.size()) {
            return false;
        }
        if (strs[idx] == "#") {
            ++idx;
            return true;
        }
        ++idx;
        return dfs(strs, idx) && dfs(strs, idx);
    }
    bool isValidSerialization(string preorder) {
        vector<string> strs;
        string2vec(preorder, strs);
        int idx = 0;
        return dfs(strs, idx) && idx == strs.size();
    }
};