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 of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Example 1:
Input: [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
Note:
1 <= preorder.length <= 100- The values of
preorderare distinct.
Solution: Recursion
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 8 ms, 10.8 MB class Solution { public: TreeNode* bstFromPreorder(vector<int>& preorder) { return build(preorder, 0, preorder.size()); } private: TreeNode* build(const vector<int>& preorder, int s, int e) { if (s >= e) return nullptr; auto root = new TreeNode(preorder[s]); int m = s; while (m < e && preorder[m] <= root->val) ++m; root->left = build(preorder, s + 1, m); root->right = build(preorder, m, e); return root; } }; |
C++/iterator
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: TreeNode* bstFromPreorder(vector<int>& preorder) { return build(begin(preorder), end(preorder)); } private: typedef vector<int>::const_iterator IT; TreeNode* build(IT s, IT e) { if (s >= e) return nullptr; auto root = new TreeNode(*s); IT m = s; while (m < e && *m <= *s) ++m; root->left = build(s + 1, m); root->right = build(m, e); return root; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment