[LeetCode] 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? 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? You may assume that the input format is always valid,for example it could never contain two consecutive commas such as? Example 1: Input: Output: "9,#"true Example 2: Input: Output: "1,#"false Example 3: Input: Output: "9,1"false
根据二叉树性质,空结点比实结点大一。
class Solution { public: bool isValidSerialization(string preorder) { stringstream ss(preorder); string val; int diff = 1; while (getline(ss,val,‘,‘)) { if (diff == 0) return false; if (val == "#") diff--; else diff++; } return diff == 0; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |