In this Leetcode Verify Preorder Serialization of a Binary Tree problem solution, One way to serialize a binary tree is to use preorder 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 '#'. 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 preorder, return true if it is a correct preorder traversal serialization of a binary tree. It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.
Problem solution in Python.
class Solution: def isValidSerialization(self, preorder: str) -> bool: preorderList = preorder.split(',') if len(preorderList)%2 != 1: return False stack = [] for node in preorderList: stack.append(node) while len(stack) >= 3 and stack[-2] == stack[-1] == '#' and stack[-3] != '#': for i in range(3): stack.pop() stack.append('#') return len(stack) == 1 and stack[0] == '#'
Problem solution in Java.
public boolean isValidSerialization(String preorder) { if(preorder.length()==1 && preorder.charAt(0)=='#'){ return true; } Deque<Boolean> stackObj = new ArrayDeque<Boolean>(); String[] nodes= preorder.split(","); for(int i=0;i<nodes.length;i++){ if(nodes[i].equals("#")){ if(stackObj.isEmpty()){ return false; }else{ while(!stackObj.isEmpty() && stackObj.getFirst()){ stackObj.removeFirst(); } if(!stackObj.isEmpty()){ stackObj.removeFirst(); stackObj.addFirst(true); }else if(i+1<nodes.length){ return false; } } }else{ stackObj.addFirst(false); } } if(stackObj.isEmpty()){ return true; } return false;[] }
Problem solution in C++.
class Solution { public: bool isValidSerialization(string preorder) { int internalNode = 0, externalNode = 0; char inString[preorder.length() + 1]; strcpy(inString, preorder.c_str()); char *nodeValue = strtok(inString, ","); while (nodeValue) { if (nodeValue[0] == '#') ++externalNode; else ++internalNode; nodeValue = strtok(NULL, ","); if (externalNode == internalNode + 1) { if (nodeValue) return false; return true; } } return false; } };
Problem solution in C.
char *checkTree(char *start) { if (*start == 0) return 0; if (*start == '#') return start + 1; char *next = start + 1; next = checkTree(next); if (next == 0) return 0; next = checkTree(next); if (next == 0) return 0; return next; } bool isValidSerialization(char * preorder){ char *c; int i; for (c = preorder, i = 0; *c; c++) { if (*c == ',') { i++; continue; } if (*c != '#') { preorder[i] = 'X'; continue; } preorder[i] = '#'; } preorder[i+1] = 0; char *end = checkTree(preorder); if (end == 0) return false; if (*end != 0) return false; return true; }
0 Comments