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


根据树的先序遍历结果,在不重构树的情况下,判断该先序遍历是否合法。

解法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,#,#变成#。

代码如下:

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() == "#";
	}
};

本代码提交AC,用时6MS。

解法2,利用度的信息。一棵二叉树通过题目中的加#策略之后,变成了一棵二叉树。这里的满是指一个节点要么有两个孩子,要么没有孩子,不存在有一个孩子的情况。(把#也看成孩子)

那么如果是叶子节点,则只贡献一个入度;如果是非叶子节点,则贡献一个入度和两个出度。所以diff=outdegree-indegree不可能是负数。

所以当来了一个节点,先--diff,因为这个节点肯定会贡献一个入度。然后判断这个节点如果是非叶子节点,则diff+=2,因为非叶子节点贡献两个出度。程序结束时,如果diff==0,则说明序列合法,否则不合法。因为就完整的树来说,入度肯定等于出度的,一条边对于父亲节点来说贡献出度,但对于孩子节点来说,贡献入度,所以总的入度和出度是相等的。

初始时,因为根节点没有入度,但是在外层while循环中,我们把根节点也看成普通的节点了。普通节点假设是有入度的,所以一进来就会--diff。所以初始时给根节点也补上一个入度,即diff=1,这样进入while之后,--diff不至于小于0。

代码如下:

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;
	}
};

本代码提交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。

代码如下:

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;
	}
};

本代码提交AC,用时6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *