Problem
Return any binary tree that matches the given preorder and postorder traversals.
Values in the traversals pre and post are distinct positive integers.
Example 1:
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] Output: [1,2,3,4,5,6,7]
Note:
1 <= pre.length == post.length <= 30pre[]andpost[]are both permutations of1, 2, ..., pre.length.- It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.
Solution: Recursion
pre = [(root) (left-child) (right-child)]
post = [(left-child) (right-child) (root)]
We need to recursively find the first node in pre.left-child from post.left-child
e.g.
pre = [(1), (2,4,5), (3,6,7)]
post = [(4,5,2), (6,7,3), (1)]
First element of left-child is 2 and the length of it is 3.
root = new TreeNode(1)
root.left = build((2,4,5), (4,5,2))
root.right = build((3,6,7), (6,7,3))
Time complexity: O(n^2)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 8 ms class Solution { public: TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) { return constructFromPrePost(cbegin(pre), cend(pre), cbegin(post), cend(post)); } private: typedef vector<int>::const_iterator VIT; TreeNode* constructFromPrePost(VIT pre_l, VIT pre_r, VIT post_l, VIT post_r) { if (pre_l == pre_r) return nullptr; TreeNode* root = new TreeNode(*pre_l); ++pre_l; --post_r; if (pre_l == pre_r) return root; VIT post_m = next(find(post_l, post_r, *pre_l)); VIT pre_m = pre_l + (post_m - post_l); root->left = constructFromPrePost(pre_l, pre_m, post_l, post_m); root->right = constructFromPrePost(pre_m, pre_r, post_m, post_r); return root; } }; |
Time complexity: O(n^2)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Running time: 60 ms """ class Solution: def constructFromPrePost(self, pre, post): def build(i, j, n): if n <= 0: return None root = TreeNode(pre[i]) if n == 1: return root k = j while post[k] != pre[i + 1]: k += 1 l = k - j + 1 root.left = build(i + 1, j, l) root.right = build(i + l + 1, k + 1, n - l - 1) return root return build(0, 0, len(pre)) |
Time complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
""" Author: Huahua Running time: 52 ms (beats 100%) """ class Solution: def constructFromPrePost(self, pre, post): def build(i, j, n): if n <= 0: return None root = TreeNode(pre[i]) if n == 1: return root k = index[pre[i + 1]] l = k - j + 1 root.left = build(i + 1, j, l) root.right = build(i + l + 1, k + 1, n - l - 1) return root index = {} for i in range(len(pre)): index[post[i]] = i return build(0, 0, len(pre)) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment