# Share my C++ solution using replace but not stack, 4ms

• ``````basic situation, leaf node: 1,#,#
advance situation 1, left child is leaf: 2,1,#,#,#
advance situation 2, right child is leaf: 2,#,1,#,#
``````

repalce node to `#`, so we got:

``````advance situation 1: 2,#,#
``````

we call the leaf node is a pattern. the ideas is iteratively repalce leaf node to `#` until no pattern to find。

So, we going to find a pattern, repalce it, and then do it again and again...

``````class Solution {
public:
bool isValidSerialization(string preorder) {
string& s = preorder;
while (s.size() >= 5) {
bool find_pattern = false;
for (int i = s.size()-1; i>= 4; i--) {
if (s[i] == '#' && s[i-2] == '#' && s[i-4] != '#') {
find_pattern = true;
int j = i-4-1;
/* find the start place of pattern */
while (j > 0 && s[j] != ',') j--;
s.replace(j+1, i-j, "#"); /* replace s[j+1, i]  to "#" */
break;  /* start a trun search from the end */
}
}
if (!find_pattern) break;
}

/* boundary: empty tree */
return (s.size() == 1 && s[0] == '#');
}
};

void test(string s, bool result) {
Solution so;
bool ret = so.isValidSerialization(s);
if (ret != result) {
cout << "test case fail: " << endl;
cout << s << endl;
cout << "true result: " << result<< endl;
cout << "false ret: " << ret << endl;
}
}

int main()
{
test("#", true); // empty tree

// true cases
test("1,#,#", true);
test("1,2,#,#,#", true);
test("9,3,4,#,#,1,#,#,2,#,6,#,#", true);

// false cases
test("1,#", false);
test("1,#,#,#,#", false);
test("9,#,#,1", false);
test("9,3,4,#,#,1,#,#,#,2,#,6,#,#", false);
return 0;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.