題目來源
判斷一棵樹的前序遍歷結(jié)果是否合法铡恕。
沒想出來怎么做翰萨，看了答案脏答，解法一是利用棧，總的思想其實(shí)就是將兩個(gè)#和一個(gè)數(shù)值替換成一個(gè)#亩鬼，到最后替換成只剩一個(gè)#殖告。
class Solution {
public:
bool isValidSerialization(string preorder) {
int n = preorder.size();
if (n == 0)
return false;
stack<char> s;
for (int i=0; i<n; i++) {
if (preorder[i] == ',')
continue;
while (preorder[i] == '#' && !s.empty() && s.top() == '#') {
s.pop();
if (s.empty())
return false;
s.pop();
}
while (preorder[i] <= '9' && preorder[i] >= '0' && i+1 < n && preorder[i+1] <= '9' && preorder[i+1] >= '0')
i++;
s.push(preorder[i]);
}
if (s.size() == 1 && s.top() == '#')
return true;
return false;
}
};
還有另一個(gè)方法用入度=出度來實(shí)現(xiàn)。
diff = outdegree - indegree
class Solution {
public:
bool isValidSerialization(string preorder) {
int n = preorder.size();
if (n == 0)
return false;
int dif = 1;
for (int i=0; i<n; i++) {
if (preorder[i] == ',')
continue;
if (--dif < 0)
return false;
if (preorder[i] != '#') {
dif += 2;
while (i < n && preorder[i] <= '9' && preorder[i] >= '0')
i++;
i--;
}
}
return dif == 0;
}
};
