{"id":4966,"date":"2019-03-09T22:08:55","date_gmt":"2019-03-10T06:08:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4966"},"modified":"2019-03-09T22:55:47","modified_gmt":"2019-03-10T06:55:47","slug":"leetcode-1008-construct-binary-search-tree-from-preorder-traversal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1008-construct-binary-search-tree-from-preorder-traversal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1008. Construct Binary Search Tree from Preorder Traversal"},"content":{"rendered":"\n

Return the root node of a binary search<\/strong> tree that matches the given preorder<\/code> traversal.<\/p>\n\n\n\n

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left<\/code> has a value <<\/code> node.val<\/code>, and any descendant of node.right<\/code> has a value ><\/code> node.val<\/code>.  Also recall that a preorder traversal displays the value of the node<\/code> first, then traverses node.left<\/code>, then traverses node.right<\/code>.)<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>[8,5,1,7,10,12]\nOutput: <\/strong>[8,5,10,1,7,null,12]\n\n<\/pre>\n\n\n\n
Note:<\/strong> <\/p>\n\n\n\n
  1. 1 <= preorder.length <= 100<\/code><\/li>
  2. The values of preorder<\/code> are distinct.<\/li><\/ol>\n\n\n\n
    Solution: Recursion<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n^2)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, 8 ms, 10.8 MB\nclass Solution {\npublic:\n  TreeNode* bstFromPreorder(vector& preorder) {\n    return build(preorder, 0, preorder.size());\n  }\nprivate:\n  TreeNode* build(const vector& preorder, int s, int e) {\n    if (s >= e) return nullptr;\n    auto root = new TreeNode(preorder[s]);\n    int m = s;\n    while (m < e && preorder[m] <= root->val) ++m;\n    root->left = build(preorder, s + 1, m);\n    root->right = build(preorder, m, e);\n    return root;\n  }\n};\n<\/pre>\n\n<\/div>
    C++\/iterator<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  TreeNode* bstFromPreorder(vector& preorder) {\n    return build(begin(preorder), end(preorder));\n  }\nprivate:\n  typedef vector::const_iterator IT;\n  TreeNode* build(IT s, IT e) {\n    if (s >= e) return nullptr;\n    auto root = new TreeNode(*s);\n    IT m = s;\n    while (m < e && *m <= *s) ++m;\n    root->left = build(s + 1, m);\n    root->right = build(m, e);\n    return root;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Return the root node of a binary search tree that matches the given preorder traversal. (Recall that a binary search tree is a binary tree where for every node, any descendant…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[457,28],"class_list":["post-4966","post","type-post","status-publish","format-standard","hentry","category-tree","tag-construct","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4966","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=4966"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4966\/revisions"}],"predecessor-version":[{"id":4969,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4966\/revisions\/4969"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}