# LeetCode889. Construct Binary Tree from Preorder and Postorder Traversal（二叉树 / 思维）

## LeetCode889. Construct Binary Tree from Preorder and Postorder Traversal（二叉树 / 思维）

• Medium
• Accepted：12,148
• Submissions：20,848

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.

### 链接

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal

### 题解

pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]

[1] 2 4 5 3 6 7 // 1为根节点
4 5 2 6 7 3 [1]

[1] [2] 4 5 3 6 7 // 2为根节点，找到2在后序遍历中的位置
4 5 [2] 6 7 3 [1] // 其中[4, 5, 2]就是1的左子树，[6, 7, 3]为1的右子树

### 代码

• Runtime: 16 ms, faster than 85.47% of C++ online submissions for Construct Binary Tree from Preorder and Postorder Traversal.
• Memory Usage: 14.7 MB, less than 24.14% of C++ online submissions for Construct Binary Tree from Preorder and Postorder Traversal.
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
int n = pre.size();
return solve(pre, post, 0, 0, n);
}

private:
TreeNode* solve(vector<int>& pre, vector<int>& post, int preStart, int postStart, int size)
{
if (size <= 0)
return NULL;
if (size == 1) // 注意一个结点的情况
{
TreeNode* bt = new TreeNode(pre[preStart]);
bt->left == NULL;
bt->right == NULL;
return bt;
}
TreeNode* bt = new TreeNode(pre[preStart]);
int root = pre[preStart+1], pos = 0; // pos代表根节点在后序遍历中位置，默认为0
for (int i = postStart; i < postStart + size; ++i)
{
if (post[i] == root)
{
pos = i;
break;
}
}
pos = (pos == 0) ? pos : pos - postStart; // 之前是从postStart的所以要减去
bt->left = solve(pre, post, preStart + 1, postStart, pos + 1);
bt->right = solve(pre, post, preStart + pos + 2, postStart + pos + 1,  size - pos - 2);
return bt;
}
};

The end.
2019年3月14日 星期四