# 原题

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 <= 30`
• `pre[]` and `post[]` are both permutations of `1, 2, ..., pre.length`.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

# 题解

```pre = [1, 2, 4]
post = [4, 2, 1]
```

```    1
2
4
```

```    1
2
4
```

## 递归 & 分治策略

```pre (root)  (left)  (right)
1,      2,4,5,  3,6,7
post (left)  (right)  (root)
4,5,2,  6,7,3,   1
```

### 代码

``````/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode *constructFromPrePost(vector<int> &pre, vector<int> &post)
{
int len = post.size();
// traversing the post
for (int i = 0; i < len; i++)
{
m[post[i]] = i;
}
return construct(pre, post, 0, len – 1, 0, len – 1);
}

TreeNode *construct(vector<int> &pre, vector<int> &post, int pre_s, int pre_e, int post_s, int post_e)
{
// boundary conditions
if (pre_s > pre_e)
return nullptr;
TreeNode *root = new TreeNode(pre[pre_s]);
if (pre_s == pre_e)
return root;

// get left & right node
int left_len = m[pre[pre_s + 1]] – post_s + 1;
root->left = construct(pre, post, pre_s + 1, pre_s + left_len, post_s, post_s + left_len – 1);
root->right = construct(pre, post, pre_s + left_len + 1, pre_e, post_s + left_len, post_e – 1);

return root;
}

private:
map<int, int> m;
};``````

### 复杂度分析

Time Complexity: O(n) ~ O(n^2)

Space Complexity: O(logn) ~ O(n)

## *迭代 & stack

### 代码

``````/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode *constructFromPrePost(vector<int> pre, vector<int> post)
{
vector<TreeNode *> s;
s.push_back(new TreeNode(pre[0]));
for (int i = 1, j = 0; i < pre.size(); ++i)
{
TreeNode *node = new TreeNode(pre[i]);
while (s.back()->val == post[j])
s.pop_back(), j++;
if (s.back()->left == NULL)
s.back()->left = node;
else
s.back()->right = node;
s.push_back(node);
}
return s[0];
}
};``````

### 复杂度分析

Time Complexity: O(n)
Space Complexity: O(n)

This site uses Akismet to reduce spam. Learn how your comment data is processed.