# 889. Construct Binary Tree from Preorder and Postorder Traversal

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.

preorder -> [root] [left subtree] [right subtree]
postorder -> [left subtree] [right substree] [root]

preorder -> [1] [2,4,5] [3,6,7]
postorder -> [4,5,2] [6,7,3] [root]

class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);
}
TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {
if (preL > preR || postL > postR) return nullptr;
TreeNode *node = new TreeNode(pre[preL]);
if (preL == preR) return node;
int idx = -1;
for (idx = postL; idx <= postR; ++idx) {
if (pre[preL + 1] == post[idx]) break;
}
node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
return node;
}
};

class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1);
}
TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR) {
if (preL > preR || postL > postR) return nullptr;
TreeNode *node = new TreeNode(pre[preL]);
if (preL == preR) return node;
int idx = find(post.begin() + postL, post.begin() + postR + 1, pre[preL + 1]) - post.begin();
node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx);
node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1);
return node;
}
};

class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
unordered_map<int, int> m;
for (int i = 0; i < post.size(); ++i) m[post[i]] = i;
return helper(pre, 0, (int)pre.size() - 1, post, 0, (int)post.size() - 1, m);
}
TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR, unordered_map<int, int>& m) {
if (preL > preR || postL > postR) return nullptr;
TreeNode *node = new TreeNode(pre[preL]);
if (preL == preR) return node;
int idx = m[pre[preL + 1]], len = (idx - postL) + 1;
node->left = helper(pre, preL + 1, preL + len, post, postL, idx, m);
node->right = helper(pre, preL + 1 + len, preR, post, idx + 1, postR - 1, m);
return node;
}
};

class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
vector<TreeNode*> st;
st.push_back(new TreeNode(pre[0]));
for (int i = 1, j = 0; i < pre.size(); ++i) {
TreeNode *node = new TreeNode(pre[i]);
while (st.back()->val == post[j]) {
st.pop_back();
++j;
}
if (!st.back()->left) st.back()->left = node;
else st.back()->right = node;
st.push_back(node);
}
return st[0];
}
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/889

Binary Tree Preorder Traversal

Binary Tree Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

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

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161286/C%2B%2B-O(N)-recursive-solution

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/163540/Java-recursive-solution-beat-99.9

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/discuss/161268/C%2B%2BJavaPython-One-Pass-Real-O(N)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation