{"id":2480,"date":"2018-04-13T08:26:50","date_gmt":"2018-04-13T15:26:50","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2480"},"modified":"2019-08-10T01:01:21","modified_gmt":"2019-08-10T08:01:21","slug":"leetcode-331-verify-preorder-serialization-of-a-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-331-verify-preorder-serialization-of-a-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 331. Verify Preorder Serialization of a Binary Tree"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

\u9898\u76ee\u5927\u610f\uff1a\u9a8c\u8bc1\u4e8c\u53c9\u6811\u524d\u5e8f\u904d\u5386\u7684\u5e8f\u5217\u5316\u662f\u5426\u5408\u6cd5\u3002<\/p>\n

https:\/\/leetcode.com\/problems\/verify-preorder-serialization-of-a-binary-tree\/description\/<\/a><\/p>\n

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\u00a0#<\/code>.<\/p>\n

     _9_\n    \/   \\\n   3     2\n  \/ \\   \/ \\\n 4   1  #  6\n\/ \\ \/ \\   \/ \\\n# # # #   # #\n<\/pre>\n
For example, the above binary tree can be serialized to the string\u00a0\"9,3,4,#,#,1,#,#,2,#,6,#,#\"<\/code>, where\u00a0#<\/code>represents a null node.<\/p>\n
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.<\/p>\n
Each comma separated value in the string must be either an integer or a character\u00a0'#'<\/code>\u00a0representing\u00a0null<\/code>pointer.<\/p>\n
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as\u00a0\"1,,3\"<\/code>.<\/p>\n
Example 1:<\/strong>
\n\"9,3,4,#,#,1,#,#,2,#,6,#,#\"<\/code>
\nReturn\u00a0true<\/code><\/p>\n
Example 2:<\/strong>
\n\"1,#\"<\/code>
\nReturn\u00a0false<\/code><\/p>\n
Example 3:<\/strong>
\n\"9,#,#,1\"<\/code>
\nReturn\u00a0false<\/code><\/p>\n
Credits:<\/b>
\nSpecial thanks to\u00a0@dietpepsi<\/a>\u00a0for adding this problem and creating all test cases.<\/p>\n
Solution: Recursion<\/strong><\/h1>\n
    \n
  1. If a node is not null, it must has two children, thus verify left subtree and right subtree recursively.<\/li>\n
  2. If a not is null, the current char must be ‘#’<\/li>\n<\/ol>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(h)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\n\/\/ Running time: 5 ms\nclass Solution {\npublic:\n  bool isValidSerialization(string preorder) {\n    int pos = 0;    \n    return isValid(preorder, pos) && pos == preorder.length();\n  }\nprivate:\n  bool isValid(const string& s, int& pos) {    \n    if (pos >= s.length()) return false;\n    if (isdigit(s[pos])) {      \n      while (isdigit(s[pos])) ++pos;\n      return isValid(s, ++pos) && isValid(s, ++pos);\n    }\n    return s[pos++] == '#';\n  }\n};<\/pre>\n","protected":false},"excerpt":{"rendered":"
    Problem \u9898\u76ee\u5927\u610f\uff1a\u9a8c\u8bc1\u4e8c\u53c9\u6811\u524d\u5e8f\u904d\u5386\u7684\u5e8f\u5217\u5316\u662f\u5426\u5408\u6cd5\u3002 https:\/\/leetcode.com\/problems\/verify-preorder-serialization-of-a-binary-tree\/description\/ 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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47,45],"tags":[177,94,4,28,296],"class_list":["post-2480","post","type-post","status-publish","format-standard","hentry","category-string","category-tree","tag-medium","tag-serialization","tag-string","tag-tree","tag-varify","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2480","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2480"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2480\/revisions"}],"predecessor-version":[{"id":5405,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2480\/revisions\/5405"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2480"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2480"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2480"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}