-
Notifications
You must be signed in to change notification settings - Fork 86
/
Verify_Preorder_Serialization_of_a_Binary_Tree.js
63 lines (49 loc) · 1.77 KB
/
Verify_Preorder_Serialization_of_a_Binary_Tree.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
Verify Preorder Serialization of a Binary Tree
https://leetcode.com/problems/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:
Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
Example 2:
Input: "1,#"
Output: false
Example 3:
Input: "9,#,#,1"
Output: false
*/
/**
* @param {string} preorder
* @return {boolean}
*/
var isValidSerialization = function (preorder) {
if (preorder.length === 0) return true;
if (preorder.charAt(0) === "#") return preorder.length === 1;
var countP = 2;
var iter = 1;
while (iter <= preorder.length && preorder.charAt(iter - 1) !== ",") iter++;
while (countP > 0 && iter < preorder.length) {
if (preorder.charAt(iter) === "#") {
countP--;
iter += 2;
} else {
countP++;
iter += 2;
while (iter <= preorder.length && preorder.charAt(iter - 1) !== ",")
iter++;
}
}
return countP === 0 && iter >= preorder.length;
};
module.exports.isValidSerialization = isValidSerialization;