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,#,# → #

不需要担心遇到x,#,#,#的情况，因为在遍历到第二个#时，就符合x,#,#的pattern了，会把x,#,#变成#。 代码如下： [cpp] 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() == "#"; } }; [/cpp] 本代码提交AC，用时6MS。 解法2，利用度的信息。一棵二叉树通过题目中的加#策略之后，变成了一棵满二叉树。这里的满是指一个节点要么有两个孩子，要么没有孩子，不存在有一个孩子的情况。（把#也看成孩子） 那么如果是叶子节点，则只贡献一个入度；如果是非叶子节点，则贡献一个入度和两个出度。所以diff=outdegree-indegree不可能是负数。 所以当来了一个节点，先–diff，因为这个节点肯定会贡献一个入度。然后判断这个节点如果是非叶子节点，则diff+=2，因为非叶子节点贡献两个出度。程序结束时，如果diff==0，则说明序列合法，否则不合法。因为就完整的树来说，入度肯定等于出度的，一条边对于父亲节点来说贡献出度，但对于孩子节点来说，贡献入度，所以总的入度和出度是相等的。 初始时，因为根节点没有入度，但是在外层while循环中，我们把根节点也看成普通的节点了。普通节点假设是有入度的，所以一进来就会–diff。所以初始时给根节点也补上一个入度，即diff=1，这样进入while之后，–diff不至于小于0。 代码如下： [cpp] 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; } }; [/cpp] 本代码提交AC，用时3MS。 解法3，也是利用度的信息。前面说了，通过题目中的策略，一棵普通二叉树已经变成了一棵满二叉树，满二叉树的特点是叶子节点的数目=非叶子节点的数目+1。简单证明如下： 假设叶子节点数为leaves，非叶子节点数为nonleaves。则总节点数为leaves+nonleaves，总边数就是leaves+nonleaves-1。一条边贡献两个度，所以总度数就是2(leaves+nonleaves-1)。从另一个角度，一个叶子节点贡献一个度，一个非叶子节点贡献3个度，根节点也是非叶子节点，但它只贡献两个读，所以总度数加起来就是leaves+3*nonleaves-1。令2(leaves+nonleaves-1)=leaves+3*nonleaves-1，就解出了leaves=nonleaves+1。 因为先序遍历是根左右，所以我们找一个满足leaves=nonleaves+1的最短前缀，如果这确实是一个合法的序列，则这个最短前缀就应该是序列本身。因为一棵满二叉树，在遍历的过程中是不会满足leaves=nonleaves+1的，只有当整棵树都遍历完之后才会满足这个条件。

     _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。]]>