题目描述
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^4
- preorder consist of integers in the range [0, 100] and ‘#’ separated by commas ‘,’.
解题思路
C++代码
class Solution {
public:
int findLUSlength(vector<string>& strs) {
int res = -1;
for(int i = 0; i < strs.size(); i++){
int j = 0;
for(j = 0; j < strs.size(); j++){
if(i == j){
continue;
}
if(check(strs[i], strs[j])){
break;
}
}
if(j == strs.size()){
res = max(res, (int)strs[i].length());
}
}
return res;
}
bool check(string a, string b){
int i = 0;
for(auto& s : b){
if(s == a[i]){
i++;
}
if(i == a.size()){
break;
}
}
return i == a.size();
}
};
