# LeetCode Exclusive Time of Functions

LeetCode Exclusive Time of Functions
Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.
Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.
A log is a string has this format : `function_id:start_or_end:timestamp`. For example, `"0:start:0"` means function 0 starts from the very beginning of time 0. `"0:end:0"` means function 0 ends to the very end of time 0.
Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function's exclusive time. You should return the exclusive time of each function sorted by their function id.
Example 1:

```Input:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
Output:[3, 4]
Explanation:
Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.
Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.
Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.
So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.
```

Note:

1. Input logs will be sorted by timestamp, NOT log id.
2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
3. Two functions won't start or end at the same time.
4. Functions could be called recursively, and will always end.
5. 1 <= n <= 100

```class Solution {
private:
struct Node {
int id_;
bool start_;
int timestamp_;
int exclude_time_;
};
void ParseLog(const string& log, Node& node) {
size_t colon_pos = log.find(':');
node.id_ = stoi(log.substr(0, colon_pos));
if (log[colon_pos + 1] == 's')
node.start_ = true;
else
node.start_ = false;
colon_pos = log.find(':', colon_pos + 1);
node.timestamp_ = stoi(log.substr(colon_pos + 1));
node.exclude_time_ = 0;
}
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> ans(n);
stack<Node> stk;
for (const auto& log : logs) {
Node node;
ParseLog(log, node);
if (node.start_) {
stk.push(node);
} else {
Node start_node = stk.top();
stk.pop();
int cur_time = node.timestamp_ - start_node.timestamp_ + 1 - start_node.exclude_time_; // caution
ans[node.id_] += cur_time; // caution
if (!stk.empty())stk.top().exclude_time_ += cur_time + start_node.exclude_time_; // caution
}
}
return ans;
}
};
```

# LeetCode Smallest Range

LeetCode Smallest Range
You have `k` lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the `k` lists.
We define the range [a,b] is smaller than range if `b-a < d-c` or `a < c` if `b-a == d-c`.
Example 1:

```Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
```

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= `k` <= 3500
3. -105 <= `value of elements` <= 105.
4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

1. i,j,k分别指向三个数组的开头，即i=j=k=0，相当于在[4,0,5]中找最大值和最小值，构成区间[0,5]，长度为5。
2. 最小值为j所在数组，所以++j，在新的数组[4,9,5]中找最大值和最小值，构成区间[4,9]，长度为5。
3. 最小值为i所在数组，所以++i，在新的数组[10,9,5]中找最大值和最小值，构成区间[5,10]，长度为5。
4. ++k，新数组[10,9,18]，区间[9,18]，长度为9。
5. ++j，新数组[10,12,18]，区间[10,18]，长度为8。
6. ++i，新数组[15,12,18]，区间[12,18]，长度为6。
7. ++j，新数组[15,20,18]，区间[15,20]，长度为5。
8. ++i，新数组[24,20,18]，区间[18,24]，长度为6。
9. ++k，新数组[24,20,22]，区间[20,24]，长度为4。
10. ++j，第二个数组遍历完毕，结束，遍历过程中，得到的长度最短的区间是[20,24]。

```class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int ansmin = 0, ansmax = 0, ansrange = INT_MAX, k = nums.size();
vector<int> ptr(k, 0);
while (true) {
bool done = false;
int curmin = INT_MAX, curmax = INT_MIN, minid = 0;
for (int i = 0; i < k; ++i) {
if (ptr[i] >= nums[i].size()) {
done = true;
break;
}
if (nums[i][ptr[i]] < curmin) {
curmin = nums[i][ptr[i]];
minid = i;
}
if (nums[i][ptr[i]] > curmax) {
curmax = nums[i][ptr[i]];
}
}
if (done)break;
if (curmax - curmin < ansrange) {
ansrange = curmax - curmin;
ansmin = curmin;
ansmax = curmax;
}
++ptr[minid];
}
return{ ansmin,ansmax };
}
};
```

```class Solution {
private:
struct Node {
int value;
int idx;
int nxt;
Node(int v, int i, int n) :value(v), idx(i), nxt(n) {};
bool operator<(const Node& nd) const {
return value > nd.value;
}
bool operator>(const Node& nd) const {
return value < nd.value;
}
};
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int ansmin = INT_MAX, ansmax = INT_MIN, ansrange = INT_MAX, k = nums.size();
priority_queue<Node> pq;
for (int i = 0; i < k; ++i) {
pq.push(Node(nums[i][0], i, 1));
if (nums[i][0] < ansmin) {
ansmin = nums[i][0];
}
ansmax = max(ansmax, nums[i][0]);
}
int curmax = ansmax;
while (true) {
int curmin = pq.top().value;
int minidx = pq.top().idx;
int minnxt = pq.top().nxt;
pq.pop();
if (curmax - curmin < ansrange) {
ansrange = curmax - curmin;
ansmin = curmin;
ansmax = curmax;
}
if (minnxt < nums[minidx].size()) {
curmax = max(curmax, nums[minidx][minnxt]);
pq.push(Node(nums[minidx][minnxt], minidx, minnxt + 1));
}
else break;
}
return{ ansmin,ansmax };
}
};
```

# LeetCode Remove K Digits

LeetCode Remove K Digits
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

```Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
```

Example 2:

```Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
```

Example 3:

```Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.```

```class Solution {
public:
string removeKdigits(string num, int k) {
if (k >= num.size())return "0";
string ans = "";
for (const auto& c : num) {
if (ans.empty() || k == 0)ans.push_back(c);
else {
while (!ans.empty() && ans.back() > c) {
ans.pop_back();
if (--k == 0)break;
}
ans.push_back(c);
}
}
while (k-- > 0 && !ans.empty()) ans.pop_back();
while (!ans.empty() && ans[0] == '0')ans.erase(ans.begin());
return ans.empty() ? "0" : ans;
}
};
```

# LeetCode Basic Calculator II

LeetCode Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, `+`, `-`, `*`, `/` operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:

```"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
```

Note: Do not use the `eval` built-in library function.

```// 优先级
unordered_map<string, int> priority = { {"+", 1},{"-", 1},{"*", 2},{"/", 2} };
class Solution {
private:
void push(stack<string> &numbers, stack<string> &opers, const string& numOrop) {
if (isdigit(numOrop[0])) {
numbers.push(numOrop);
}
else {
if (numOrop == ")") {
while (opers.top() != "(") {
numbers.push(opers.top());
opers.pop();
}
opers.pop();
}
else if (numOrop == "(") {
opers.push(numOrop);
}
else if (opers.empty() || opers.top() == "(") {
opers.push(numOrop);
}
else if (priority[numOrop] > priority[opers.top()]) {
opers.push(numOrop);
}
else {
while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) {
numbers.push(opers.top());
opers.pop();
}
opers.push(numOrop);
}
}
}
// 中缀转后缀表达式
list<string> in2post(const string& s) {
stack<string> numbers, opers;
int start = 0, end = 1, n = s.size();
while (start < n) {
while (start < n&&s[start] == ' ')++start;
if (start >= n)break;
if (isdigit(s[start])) {
end = start + 1;
while (end < n&&isdigit(s[end]))++end;
string num = s.substr(start, end - start);
push(numbers, opers, num);
start = end;
}
else {
string op = string(1, s[start]);
push(numbers, opers, op);
++start;
}
}
while (!opers.empty()) {
numbers.push(opers.top());
opers.pop();
}
list<string> ans;
while(!numbers.empty()) {
ans.push_front(numbers.top());
numbers.pop();
}
return ans;
}
// 求值后缀表达式的值
int eval(list<string>& post) {
int ans = 0;
stack<int> numbers;
for (const auto& s : post) {
if (priority.find(s) != priority.end()) {
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
if (s == "+")numbers.push(num1 + num2);
else if (s == "-")numbers.push(num1 - num2);
else if (s == "*")numbers.push(num1*num2);
else numbers.push(num1 / num2);
}
else numbers.push(stoi(s));
}
return numbers.top();
}
public:
int calculate(string s) {
list<string> ans = in2post(s);
return eval(ans);
}
};
```

# LeetCode Basic Calculator

LeetCode Basic Calculator
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open `(` and closing parentheses `)`, the plus `+` or minus sign `-`, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:

```"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
```

Note: Do not use the `eval` built-in library function.

• 如果是操作数，直接压入numbers
• 如果是操作符op：
1. 如果op为左括号“（”，则直接把op压入opers
2. 如果op为右括号“）”，则把opers的运算符不断弹栈并压入numbers，直到栈顶为左括号“（”，此时将这一对括号丢弃
3. 如果opers为空，或者opers栈顶为左括号“（”，则直接把op压入opers
4. 此时，栈顶肯定不可能是括号了，如果op的优先级高于opers栈顶的优先级，则直接把op压入opers
5. 否则，把opers栈顶的运算符不断弹栈并压入numbers，直到栈顶为左括号，或者op的优先级高于opers栈顶的优先级。把op压入opers

```// 优先级
unordered_map<string, int> priority = { {"+", 1},{"-", 1},{"*", 2},{"/", 2} };
class Solution {
private:
void push(stack<string> &numbers, stack<string> &opers, const string& numOrop) {
if (isdigit(numOrop[0])) {
numbers.push(numOrop);
}
else {
if (numOrop == ")") {
while (opers.top() != "(") {
numbers.push(opers.top());
opers.pop();
}
opers.pop();
}
else if (numOrop == "(") {
opers.push(numOrop);
}
else if (opers.empty() || opers.top() == "(") {
opers.push(numOrop);
}
else if (priority[numOrop] > priority[opers.top()]) {
opers.push(numOrop);
}
else {
while (!opers.empty() && opers.top() != "(" && priority[numOrop] <= priority[opers.top()]) {
numbers.push(opers.top());
opers.pop();
}
opers.push(numOrop);
}
}
}
// 中缀转后缀表达式
list<string> in2post(const string& s) {
stack<string> numbers, opers;
int start = 0, end = 1, n = s.size();
while (start < n) {
while (start < n&&s[start] == ' ')++start;
if (start >= n)break;
if (isdigit(s[start])) {
end = start + 1;
while (end < n&&isdigit(s[end]))++end;
string num = s.substr(start, end - start);
push(numbers, opers, num);
start = end;
}
else {
string op = string(1, s[start]);
push(numbers, opers, op);
++start;
}
}
while (!opers.empty()) {
numbers.push(opers.top());
opers.pop();
}
list<string> ans;
while(!numbers.empty()) {
ans.push_front(numbers.top());
numbers.pop();
}
return ans;
}
// 求值后缀表达式的值
int eval(list<string>& post) {
int ans = 0;
stack<int> numbers;
for (const auto& s : post) {
if (priority.find(s) != priority.end()) {
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
if (s == "+")numbers.push(num1 + num2);
else if (s == "-")numbers.push(num1 - num2);
else if (s == "*")numbers.push(num1*num2);
else numbers.push(num1 / num2);
}
else numbers.push(stoi(s));
}
return numbers.top();
}
public:
int calculate(string s) {
list<string> ans = in2post(s);
return eval(ans);
}
};
```

# LeetCode Mini Parser

LeetCode Mini Parser
Given a nested list of integers represented as a string, implement a parser to deserialize it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Note: You may assume that the string is well-formed:

• String is non-empty.
• String does not contain white spaces.
• String contains only digits `0-9`, `[`, `-` `,`, `]`.

Example 1:

```Given s = "324",
You should return a NestedInteger object which contains a single integer 324.
```

Example 2:

```Given s = "[123,[456,[789]]]",
Return a NestedInteger object containing a nested list with 2 elements:
1. An integer containing value 123.
2. A nested list containing two elements:
i.  An integer containing value 456.
ii. A nested list with one element:
a. An integer containing value 789.```

```class Solution {
public:
NestedInteger deserialize(string s) {
auto isnumber = [](char c) {return c == '-' || isdigit(c); };
stack<NestedInteger> stk;
stk.push(NestedInteger());
for (auto it = s.begin(); it != s.end();) {
if (isnumber(*it)) {
auto it2 = find_if_not(it, s.end(), isnumber);
int v = stoi(string(it, it2));
it = it2;
}
else {
if (*it == '[') {
stk.push(NestedInteger());
}
else if (*it == ']') {
NestedInteger tmp = stk.top();
stk.pop();
}
++it;
}
}
return stk.top().getList().front();
}
};
```

```class Solution {
private:
NestedInteger deserialize(istringstream &in) {
int number;
if (in >> number)
return NestedInteger(number);
in.clear();
in.get();
NestedInteger list;
while (in.peek() != ']') {
if (in.peek() == ',')in.get();
}
in.get();
return list;
}
public:
NestedInteger deserialize(string s) {
istringstream in(s);
return deserialize(in);
}
};
```

# LeetCode Find K Pairs with Smallest Sums

LeetCode Find K Pairs with Smallest Sums
You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
Define a pair (u,v) which consists of one element from the first array and one element from the second array.
Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
Example 1:

```Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
Return: [1,2],[1,4],[1,6]
The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
```

Example 2:

```Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
Return: [1,1],[1,1]
The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
```

Example 3:

```Given nums1 = [1,2], nums2 = [3],  k = 3
Return: [1,3],[2,3]
All possible pairs are returned from the sequence:
[1,3],[2,3]```

```class Solution {
private:
struct P {
int x, y;
P(int x_, int y_) :x(x_), y(y_) {};
bool operator<(const P& p) const{
return (this->x + this->y) < (p.x + p.y);
}
bool operator>(const P& p) const {
return (this->x + this->y) > (p.x + p.y);
}
};
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<P> pq; // 大顶堆
for (int i = 0; i < nums1.size(); ++i) {
for (int j = 0; j < nums2.size(); ++j) {
P p(nums1[i], nums2[j]);
pq.push(p);
if (pq.size() > k)pq.pop(); // 弹出最大元素
}
}
vector<pair<int, int>> ans;
while (!pq.empty()) { // 保留的都是最小元素
ans.push_back(pair<int, int>(pq.top().x, pq.top().y));
pq.pop();
}
return ans;
}
};
```

# LeetCode Tag Validator

LeetCode Tag Validator
Given a string representing a code snippet, you need to implement a tag validator to parse the code and return whether it is valid. A code snippet is valid if all the following rules hold:

1. The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.
2. A closed tag (not necessarily valid) has exactly the following format : `<TAG_NAME>TAG_CONTENT</TAG_NAME>`. Among them, `<TAG_NAME>` is the start tag, and `</TAG_NAME>` is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.
3. A valid `TAG_NAME` only contain upper-case letters, and has length in range [1,9]. Otherwise, the `TAG_NAME` is invalid.
4. A valid `TAG_CONTENT` may contain other valid closed tags, cdata and any characters (see note1) EXCEPT unmatched `<`, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the `TAG_CONTENT` is invalid.
5. A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.
6. A `<` is unmatched if you cannot find a subsequent `>`. And when you find a `<` or `</`, all the subsequent characters until the next `>` should be parsed as TAG_NAME (not necessarily valid).
7. The cdata has the following format : `<![CDATA[CDATA_CONTENT]]>`. The range of `CDATA_CONTENT` is defined as the characters between `<![CDATA[` and the first subsequent`]]>`.
8. `CDATA_CONTENT` may contain any characters. The function of cdata is to forbid the validator to parse `CDATA_CONTENT`, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters.

Valid Code Examples:

```Input: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: True
Explanation:
The code is wrapped in a closed tag : <DIV> and </DIV>.
The TAG_NAME is valid, the TAG_CONTENT consists of some characters and cdata.
Although CDATA_CONTENT has unmatched start tag with invalid TAG_NAME, it should be considered as plain text, not parsed as tag.
So TAG_CONTENT is valid, and then the code is valid. Thus return true.
Input: "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
Output: True
Explanation:
We first separate the code into : start_tag|tag_content|end_tag.
start_tag -> "<DIV>"
end_tag -> "</DIV>"
tag_content could also be separated into : text1|cdata|text2.
text1 -> ">>  ![cdata[]] "
cdata -> "<![CDATA[<div>]>]]>", where the CDATA_CONTENT is "<div>]>"
text2 -> "]]>>]"
The reason why start_tag is NOT "<DIV>>>" is because of the rule 6.
The reason why cdata is NOT "<![CDATA[<div>]>]]>]]>" is because of the rule 7.
```

Invalid Code Examples:

```Input: "<A>  <B> </A>   </B>"
Output: False
Explanation: Unbalanced. If "<A>" is closed, then "<B>" must be unmatched, and vice versa.
Input: "<DIV>  div tag is not closed  <DIV>"
Output: False
Input: "<DIV>  unmatched <  </DIV>"
Output: False
Input: "<DIV> closed tags with invalid tag name  <b>123</b> </DIV>"
Output: False
Input: "<DIV> unmatched tags with invalid tag name  </1234567890> and <CDATA[[]]>  </DIV>"
Output: False
Input: "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>"
Output: False
```

Note:

1. For simplicity, you could assume the input code (including the any characters mentioned above) only contain `letters`, `digits`, `'<'`,`'>'`,`'/'`,`'!'`,`'['`,`']'` and `' '`.

```class Solution {
private:
bool checkTag(const string &tag) {
if (tag.size() < 1 || tag.size() > 9)return false;
for (const auto &c : tag) {
if (!isupper(c))return false;
}
return true;
}
public:
bool isValid(string code) {
stack<string> stk;
int i = 0;
while (i < code.size()) {
if (i > 0 && stk.empty())return false;
if (code.substr(i, 9) == "<![CDATA[") {
int end = code.find("]]>", i);
if (end == string::npos)return false;
i = end + 3;
}
else if (code.substr(i, 2) == "</") {
int end = code.find('>', i);
if (end == string::npos)return false;
string tag = code.substr(i + 2, end - i - 2);
if (!checkTag(tag))return false;
if (stk.empty() || stk.top() != tag)return false;
else stk.pop();
i = end + 1;
}
else if (code[i] == '<') {
int end = code.find('>', i);
if (end == string::npos)return false;
string tag = code.substr(i + 1, end - i - 1);
if (!checkTag(tag))return false;
stk.push(tag);
i = end + 1;
}
else {
++i;
}
}
return stk.empty();
}
};
```

# LeetCode Kth Smallest Element in a Sorted Matrix

LeetCode Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:

```matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
```

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

```class Solution {
private:
struct Node {
int val, row, col;
Node(int v = 0, int r = 0, int c = 0) :val(v), row(r), col(c) {};
friend bool operator<(const Node& n1, const Node& n2) {
return n1.val > n2.val;
}
};
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
priority_queue<Node> pn;
for (int i = 0; i < n; ++i)pn.push(Node(matrix[i][0], i, 0));
Node t;
while (k--) {
t = pn.top();
pn.pop();
if (t.col < n - 1)pn.push(Node(matrix[t.row][t.col + 1], t.row, t.col + 1));
}
return t.val;
}
};
```

```class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
while (left <= right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += upper_bound(matrix[i].begin(), matrix[i].end(), mid) - matrix[i].begin();
}
if (cnt < k)left = mid + 1;
else right = mid - 1;
}
return left;
}
};
```

```class Solution {
private:
int count_less_equal(vector<vector<int>>& matrix, int num) {
int n = matrix.size(), i = n - 1, j = 0, cnt = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] <= num) {
cnt += i + 1;
++j;
}
else --i;
}
return cnt;
}
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size(), left = matrix[0][0], right = matrix[n - 1][n - 1];
while (left <= right) {
int mid = left + (right - left) / 2;
int cnt = count_less_equal(matrix, mid);
if (cnt < k)left = mid + 1;
else right = mid - 1;
}
return left;
}
};
```

# LeetCode Verify Preorder Serialization of a Binary Tree

LeetCode Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use pre-order 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 `#`.

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

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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
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"`.
Example 1:
`"9,3,4,#,#,1,#,#,2,#,6,#,#"`
Return `true`
Example 2:
`"1,#"`
Return `false`
Example 3:
`"9,#,#,1"`
Return `false`

• 9,3,4,#,# → 9,3,#
• 9,3,#,1,#,# → 9,3,#,# → 9,#
• 9,#,2,#,6,#,# → 9,#,2,#,# → 9,#,# → #

```class Solution {
public:
bool isValidSerialization(string preorder) {
stack<string> stk;
int i = 0, j = 0, n = preorder.size();
while (j < n) {
while (j < n&&preorder[j] != ',')++j;
string node = preorder.substr(i, j - i);
if (node == "#") {
while (!stk.empty() && stk.top() == "#") {
stk.pop();
if (stk.empty())return false;
stk.pop();
}
}
stk.push(node);
i = ++j;
}
return stk.size() == 1 && stk.top() == "#";
}
};
```

```class Solution {
public:
bool isValidSerialization(string preorder) {
int i = 0, j = 0, n = preorder.size(), diff = 1;
while (j < n) {
while (j < n&&preorder[j] != ',')++j;
string node = preorder.substr(i, j - i);
if (--diff < 0)return false;
if (node != "#")diff += 2;
i = ++j;
}
return diff == 0;
}
};
```

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

```class Solution3 {
public:
bool isValidSerialization(string preorder) {
int leaves = 0, nonleaves = 0;
int i = 0, j = 0, n = preorder.size();
while (j < n) {
while (j < n&&preorder[j] != ',')++j;
string node = preorder.substr(i, j - i);
if (node == "#")++leaves;
else ++nonleaves;
i = ++j;
if (leaves - nonleaves == 1 && j < n)return false;
}
return leaves - nonleaves == 1;
}
};
```