|
| 1 | +// Source : https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/ |
| 2 | +// Author : Hao Chen |
| 3 | +// Date : 2017-01-06 |
| 4 | + |
| 5 | +/*************************************************************************************** |
| 6 | + * |
| 7 | + * One way to serialize a binary tree is to use pre-order traversal. When we encounter |
| 8 | + * a non-null node, we record the node's value. If it is a null node, we record using a |
| 9 | + * sentinel value such as #. |
| 10 | + * |
| 11 | + * _9_ |
| 12 | + * / \ |
| 13 | + * 3 2 |
| 14 | + * / \ / \ |
| 15 | + * 4 1 # 6 |
| 16 | + * / \ / \ / \ |
| 17 | + * # # # # # # |
| 18 | + * |
| 19 | + * For example, the above binary tree can be serialized to the string |
| 20 | + * "9,3,4,#,#,1,#,#,2,#,6,#,#", where # represents a null node. |
| 21 | + * |
| 22 | + * Given a string of comma separated values, verify whether it is a correct preorder |
| 23 | + * traversal serialization of a binary tree. Find an algorithm without reconstructing |
| 24 | + * the tree. |
| 25 | + * |
| 26 | + * Each comma separated value in the string must be either an integer or a character |
| 27 | + * '#' representing null pointer. |
| 28 | + * |
| 29 | + * You may assume that the input format is always valid, for example it could never |
| 30 | + * contain two consecutive commas such as "1,,3". |
| 31 | + * |
| 32 | + * Example 1: |
| 33 | + * "9,3,4,#,#,1,#,#,2,#,6,#,#" |
| 34 | + * Return true |
| 35 | + * Example 2: |
| 36 | + * "1,#" |
| 37 | + * Return false |
| 38 | + * Example 3: |
| 39 | + * "9,#,#,1" |
| 40 | + * Return false |
| 41 | + * |
| 42 | + * Credits:Special thanks to @dietpepsi for adding this problem and creating all test |
| 43 | + * cases. |
| 44 | + ***************************************************************************************/ |
| 45 | + |
| 46 | +classSolution { |
| 47 | +public: |
| 48 | + |
| 49 | +// we know the following facts: |
| 50 | +// 1) if we met a non-null node, then this node will generate two child node. |
| 51 | +// 2) if we met a null node, then this node will generate zero child node. |
| 52 | +// |
| 53 | +// so the idea is, |
| 54 | +// 1) we can have a counter to calculate how many node we are going to expect |
| 55 | +// 2) once we have the expected node, then we can decrease the counter. |
| 56 | +// 3) finally, we will check the counter is zero or not. |
| 57 | +// |
| 58 | +// the algorithm as below: |
| 59 | +// 1) when we meet a non-null node, just simply do `counter++`. because: |
| 60 | +// 1.1) we will expect 2 more node after, then we do `counter += 2`. |
| 61 | +// 1.2) but the current node also meet the expection of parent node , so, it need remove 1 in counter. |
| 62 | +// finally, the `counter = counbter + 2 -1` |
| 63 | +// 2) when we meet a null node, just simply do `counter--`. |
| 64 | + |
| 65 | +boolisValidSerialization(string preorder) { |
| 66 | + vector<string> list; |
| 67 | +split(preorder,',', list); |
| 68 | +//we initailize the counter as 1, |
| 69 | +//because we expect at lease 1 node in the tree. |
| 70 | +int node_expected =1; |
| 71 | +for (auto node : list) { |
| 72 | +if (node_expected ==0)returnfalse; |
| 73 | + node =="#" ? node_expected-- : node_expected++; |
| 74 | + } |
| 75 | +return node_expected ==0; |
| 76 | + } |
| 77 | + |
| 78 | +voidsplit(const string &s,char delim, vector<string> &elems) { |
| 79 | + stringstreamss(s); |
| 80 | + string item; |
| 81 | +while (getline(ss, item, delim)) { |
| 82 | + elems.push_back(item); |
| 83 | + } |
| 84 | + } |
| 85 | +}; |