【leetcode】331. 验证二叉树的前序序列化（verify-preorder-serialization-of-a-binary-tree）（栈）[中等]

链接

https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/

耗时

解题：21 min
题解：27 min

题意

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

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

例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。

你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,3” 。

思路

题目可以理解为，字符串中只含有叶子节点（‘#’）和非叶子节点（非‘#’），判断字符串是否是一棵树的前序序列。前序序列是先访问根节点然后是左右子树，所以如果左右子树的前序序列都合理且根节点存在则当前树合理。

使用栈，基本思想是当前节点的两棵子树都合理则把当前节点消掉。具体地，如果遇到非叶节点，将其入栈，遇到叶子节点则检查栈顶是否是叶子节点，如果是说明栈顶元素的前一个元素如果是非叶子节点则它们合理，将它们这棵树变成叶子节点，即将它们从栈中弹出，并准备入栈一个叶子节点，而这相当于遇到一个叶子节点，所以继续检查，直到栈顶元素不再是叶子节点，然后入栈一个叶子节点。

最后如果遍历完成后栈中只剩下一个叶子节点则说明这个前序序列合理。

时间复杂度： O ( n ) O(n) O(n)

AC代码

class Solution {
public:
    bool isValidSerialization(string preorder) {
        stack<int> st;
        int n = preorder.size();
        for(int i = 0; i < n; ++i) {
            if(preorder[i] == ',') {
                continue;
            }
            else if(preorder[i] == '#') {
                while(!st.empty() && st.top() == '#') {
                    if(st.size() < 2) return false;
                    st.pop();
                    st.pop();
                }
                st.push('#');
            }
            else {
                while(preorder[i] >= '0' && preorder[i] <= '9') {
                    i++;
                }
                st.push('*');
            }
        }
        return st.size() == 1 && st.top() == '#';
    }
};