LeetCode *331. 验证二叉树的前序序列化（栈）

题目

思路1：入度出度

LeetCode题解思路：题解

代码语言：javascript复制

class Solution {
public:
    bool isValidSerialization(string preorder) {
        vector<string> str;
        int diff = 1;
        string s;
        for (int i = 0; i < preorder.size(); i  ) {
            if (preorder[i] == ',') {
                str.push_back(s);
                s = "";
                continue;
            }
            s  = preorder[i];
        }
        str.push_back(s);
        for (int i = 0; i < str.size(); i  ) {
            diff--;
            if (diff < 0) return false;
            if (str[i] != "#") diff  = 2;
        }
        return diff == 0;
    }
};

思路2：栈

代码语言：javascript复制

class Solution {
public:
    bool isValidSerialization(string preorder) {
        vector<string> st;
        vector<string> str;
        string s;
        for (int i = 0; i < preorder.size(); i  ) {
            if (preorder[i] == ',') {
                str.push_back(s);
                s = "";
                continue;
            }
            s  = preorder[i];
        }
        str.push_back(s);
        for (int i = 0; i < str.size(); i  ) {
            st.push_back(str[i]);
            while (st.size() >= 3 && st[st.size() - 1] == "#" && st[st.size() - 2] == "#" && st[st.size() - 3] != "#") {
                st.pop_back();
                st.pop_back();
                st.pop_back();
                st.push_back("#");
            }
        }
        if (st.size() == 1 && st.back() == "#") {
            return true;
        }
        return false;
    }
};

ode

0 人点赞