p331

发表于 | 分类于 |

LeetCode p331 Verify Preorder Serialization of a Binary Tree 题解

1.题目：

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

题意：

分析一个字符串，是否是一个二叉树的前顺遍历。
所有的null都对应一个”#”。

2.解题思路:

把#看成一个无法延续的节点，这棵树底部所有的节点都要以”#”终止。
令开头为1。每碰到一个不为空的子节点就意味着总数多加2个。
每次遍历减去当前的节点，即减1.
整个过程ans不能为负（前序遍历）
遍历完成ans为0则为真。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
public class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] c = preorder.split(",");
		int ans = 1;
		for (String a : c) {
			ans--;
			if (ans < 0)
				break;
			if (!a.equals("#")) {

				ans += 2;
			}
			

		}
		return ans == 0;
    }
}

4.一些总结：