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
根据树的先序遍历结果，在不重构树的情况下，判断该先序遍历是否合法。 解法1，使用栈。因为先序遍历的顺序是根左右，如果我们遇到序列x,#,#，其中x不是#时，说明x的左右孩子都是#，此时，我们将x,#,#替换为#，表示将以x为根的子树替换为一个#。如此循环，如果栈中最终只剩下一个#，说明该序列合法。 比如样例”9,3,4,#,#,1,#,#,2,#,6,#,#”：
- 9,3,4,#,# → 9,3,#
- 9,3,#,1,#,# → 9,3,#,# → 9,#
- 9,#,2,#,6,#,# → 9,#,2,#,# → 9,#,# → #
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
上面这棵树，虽然在遍历到节点2时，如果不再往下遍历了，看起来也是满二叉树，但是2是有孩子的，所以会被判断为nonleaves，所以还是不满足leaves=nonleaves+1。
代码如下：
[cpp]
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;
}
};
[/cpp]
本代码提交AC，用时6MS。]]>