首页 > 代码库 > Verify Preorder Serialization of a Binary Tree -- LeetCode
Verify Preorder Serialization of a Binary Tree -- LeetCode
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
思路：将字符串按照逗号分隔，然后依次读入节点。用一个栈来记录当前的节点是左孩子还是右孩子。
1 class Solution { 2 public: 3 bool isValidSerialization(string preorder) { 4 istringstream iss(preorder); 5 string node; 6 stack<bool> leftPathTrack; 7 bool tracked = false; 8 while (getline(iss, node, ‘,‘)) { 9 if (tracked && leftPathTrack.empty()) return false;10 tracked = true;11 if (node == "#") {12 //for the case the root node is ‘#‘13 if (leftPathTrack.empty()) continue;14 /*15 If the current node is left child, pop it and mark the next node as right.16 Else, pop all the nodes in the stack until the top node is a left child,17 pop it and mark the next node as right.18 */19 while (!leftPathTrack.empty() && !leftPathTrack.top()) 20 leftPathTrack.pop();21 if (!leftPathTrack.empty()) {22 leftPathTrack.pop();23 leftPathTrack.push(false);24 }25 } else {26 leftPathTrack.push(true);27 }28 }29 return leftPathTrack.empty();30 }31 };
Verify Preorder Serialization of a Binary Tree -- LeetCode