Description#
Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.
If there exist multiple answers, you can return any of them.
Example 1:
Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
Example 2:
Input: preorder = [1], postorder = [1]
Output: [1]
Constraints:
1 <= preorder.length <= 301 <= preorder[i] <= preorder.length- All the values of
preorder are unique. postorder.length == preorder.length1 <= postorder[i] <= postorder.length- All the values of
postorder are unique. - It is guaranteed that
preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructFromPrePost(
self, preorder: List[int], postorder: List[int]
) -> TreeNode:
n = len(preorder)
if n == 0:
return None
root = TreeNode(preorder[0])
if n == 1:
return root
for i in range(n - 1):
if postorder[i] == preorder[1]:
root.left = self.constructFromPrePost(
preorder[1 : 1 + i + 1], postorder[: i + 1]
)
root.right = self.constructFromPrePost(
preorder[1 + i + 1 :], postorder[i + 1 : -1]
)
return root
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<int, int> postMap;
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
for (int i = 0; i < postorder.size(); i++) {
postMap[postorder[i]] = i;
}
return build(preorder, 0, preorder.size() - 1, postorder, 0, postorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, int prel, int prer, vector<int>& postorder, int postl, int postr) {
if (prel > prer) return nullptr;
TreeNode* root = new TreeNode(preorder[prel]);
if (prel == prer) return root;
int leftRootIndex = postMap[preorder[prel + 1]];
int leftLength = leftRootIndex - postl + 1;
root->left = build(preorder, prel + 1, prel + leftLength, postorder, postl, leftRootIndex);
root->right = build(preorder, prel + leftLength + 1, prer, postorder, leftRootIndex + 1, postr - 1);
return root;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
postMap := make(map[int]int)
for index, v := range postorder {
postMap[v] = index
}
var dfs func(prel, prer, postl, postr int) *TreeNode
dfs = func(prel, prer, postl, postr int) *TreeNode {
if prel > prer {
return nil
}
root := &TreeNode{Val: preorder[prel]}
if prel == prer {
return root
}
leftRootIndex := postMap[preorder[prel+1]]
leftLength := leftRootIndex - postl + 1
root.Left = dfs(prel+1, prel+leftLength, postl, leftRootIndex)
root.Right = dfs(prel+leftLength+1, prer, leftRootIndex+1, postr-1)
return root
}
return dfs(0, len(preorder)-1, 0, len(postorder)-1)
}
|
