[Leetcode 331] Verify Preorder Serialization of a Binary Tree

作者 Shilei Tian 日期 2017-02-13
[Leetcode 331] 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 val id, 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

解题思路

这道题目其实还是蛮有意思的,只不过刚拿到手的时候一点思路都没有,看过答案之后才知道这道题目有两种思路可以解决,一种是利用栈,有点模拟先序遍历的意思;另外一种是利用类似图中的出度和入度来解决。两者的时间复杂度都是 O(n),所以在 Leetcode 上面运行完了都是 6ms,不过两种思路都值得认真学习。

利用栈

先序遍历利用递归来做的话,相当于每遇到一个节点就将其压入栈中,然后遍历它的左子树。当遍历到空树时,就从栈中取出栈顶元素,再遍历其右子树。这道题目可以用这种思想来解决。考虑给出的先序遍历,如果有两个连续的 #,就说明这两个连续的 # 前面那个节点一定是个叶子结点,它就要从栈中弹出来,因为已经没有遍历它的可能。那将来如何来标记它的父结点也被遍历完了呢?这里就是一个小技巧。每次检查先序遍历那个字符串,如果遇到的是一个 # 并且此时栈顶元素不是 #,那么就将这个 # 压入栈中,检查下一位;如果此时栈顶元素是 #,就说明,我们遇到了一个叶子结点,我们需要将栈顶的这个 # 弹出,再将紧接着栈顶的元素也弹出,因为这个紧接着的这个元素就是叶子结点。这就相当于下面这个过程:

_9_
/ \
3 2
/ \ / \
# # # #

合法的先序遍历的字符串应该是 "9,3,#,#,2,#,#",我们暂时只考虑 9 这个结点左子树,那当我们读到 "9,3,#" 时,此时栈的状态应该是 9,3,#,然后我们又读到了一个 #,这时候它发现栈顶元素也是 #,就将其弹出两次,压入自己,这时候栈就变成 9,#,而树就相当于变成:

_9_
/ \
# 2
/ \
# #

这样我们就标记了 9 的左子树已经变成空,表示它已经遍历完了。当我们将子树 2 也遍历完了的时候,树就相当于变成:

_9_
/ \
# #

此时栈应该是 9,#,然后我们当前还是 #,继续弹出两次栈就空了,再压入自己(#),结束的时候栈的大小为 1,并且里面的元素一定是 #

上面讲的就是合法的先序遍历会产生的结果,那么有可能在哪些地方会出现非法呢?第一个,就是我们每次弹出栈的时候要弹出两次,那么如果我们弹出一次时就发现栈空了,那么自然就说明我们前面读取的先序遍历是非法的,此时就 return false; 即可。那么第二个,就是我们最终的状态,肯定是栈的大小为 1,并且栈顶元素是 #,如果不是这样的,也是非法的。

最终代码如下:

class Solution {
public:
bool isValidSerialization(string preorder) {
if (preorder.empty()) {
return false;
}
vector<string> tokens = split(preorder, ',');
if (tokens.empty()) {
return false;
}
stack<string> st;
for (int i = 0; i < tokens.size(); ++i) {
string cur = tokens[i];
while (cur == "#" && !st.empty() && st.top() == "#") {
st.pop();
if (st.empty()) {
return false;
}
st.pop();
}
st.push(cur);
}
return st.size() == 1 && st.top() == "#";
}
private:
vector<string> split(const string& str, const char f) {
string mid;
vector<string> res;
for (auto ch : str) {
if (ch == f) {
res.push_back(mid);
mid.clear();
} else {
mid.push_back(ch);
}
}
if (!mid.empty()) {
res.push_back(mid);
}
return res;
}
};

由于 C++ 没有 split 函数,并且题目已经告知假设所有的输入都是合法的,因此这里自己写一个简单的 split 函数。

利用出入度

这一种思路很新颖,用图论的方法来解决树的问题,这是第一次看到。在这种思路中,我们将 # 当作叶子结点,那么除了叶子结点外,其余的所有节点都能为整个图贡献 1 入度(从父结点来,当然除根结点外)和 2 出度,# 结点只能贡献 1 入度。整棵树构成的图最终出度与入度的差是 0。那么好了,我们用一个变量 diff 来记录出度与入度的差,当我们读取到 # 时,# 无法贡献出度,只能贡献入度,那么对于 diff 造成的影响,就是让 diff1;当我们读取到其他结点时,对 diff 造成的影响是增加两个出度,那么 diff1。最终扫描下来,如果 diff0,就说明我们的这个先序遍历字符串是合法的,否则就是非法的。并且,这里面还有一个关键点,在于合法的 diff 永远不能为负数。因为每次我们引入一个普通结点时候,都会贡献两个出度,引入一个叶子结点时候贡献一个入度,一个出度对应一个入度,如果入度比出度多了,就说明叶子结点比分支还多,这个显然是非法的。

最终代码如下:

class Solution {
public:
bool isValidSerialization(string preorder) {
if (preorder.empty()) {
return false;
}
vector<string> tokens;
split(preorder, ',', tokens);
if (tokens.empty()) {
return false;
}
int diff = 1;
for (auto token : tokens) {
if (--diff < 0) {
return false;
}
if (token != "#") {
diff += 2;
}
}
return diff == 0;
}
private:
void split(const string& str, const char f, vector<string>& tokens) {
string mid;
for (auto ch : str) {
if (ch == f) {
tokens.push_back(mid);
mid.clear();
} else {
mid.push_back(ch);
}
}
if (!mid.empty()) {
tokens.push_back(mid);
}
}
};

上面将 tokens 的复制构造变成引用,以为会有一些提升,然而并没有……

总结

一道非常有趣的题目,两种不同的解决思路,用图的角度来考虑树,这个确实是一种新思路。