Algorithm
Problem Name: 889. Construct Binary Tree from Preorder and Postorder Traversal
Problem Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
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 <= 30
1 <= preorder[i] <= preorder.length
- All the values of
preorder
are unique. postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
- All the values of
postorder
are unique. - It is guaranteed that
preorder
andpostorder
are the preorder traversal and postorder traversal of the same binary tree.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
if (pre.empty()) {
return NULL;
}
TreeNode* root = new TreeNode(pre[0]);
if(pre.size() == 1) {
return root;
}
vector<int>preLeft, preRight, postLeft, postRight;
int rootLeft = pre[1];
int pos = find(post.begin(), post.end(), rootLeft) - post.begin();
postLeft.assign(post.begin(), post.begin() + pos + 1);
postRight.assign(post.begin() + pos + 1, post.end() - 1);
preLeft.assign(pre.begin() + 1, pre.begin() + 1 + pos + 1);
preRight.assign(pre.begin() + 1 + pos + 1, pre.end());
root->left = constructFromPrePost(preLeft, postLeft);
root->right = constructFromPrePost(preRight, postRight);
return root;
}
};
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
Map map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
int[] postIdx = {postorder.length - 1};
return helper(postorder, map, 0, inorder.length - 1, postIdx);
}
private TreeNode helper(int[] postorder, Map < Integer, Integer> map, int leftIdx, int rightIdx, int[] postIdx) {
if (leftIdx > rightIdx) {
return null;
}
TreeNode root = new TreeNode(postorder[postIdx[0]--]);
int index = map.get(root.val);
root.right = helper(postorder, map, index + 1, rightIdx, postIdx);
root.left = helper(postorder, map, leftIdx, index - 1, postIdx);
return root;
}
}
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const constructFromPrePost = function(pre, post) {
let i = 0,
j = 0
return (function dfs() {
let val = pre[i++]
let node = new TreeNode(val)
if (val !== post[j]) node.left = dfs()
if (val !== post[j]) node.right = dfs()
j++
return node
})()
}
Copy The Code &
Try With Live Editor
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def constructFromPrePost(self, pre, post):
if pre:
root = TreeNode(pre.pop(0))
post.pop()
if pre:
if pre[0] == post[-1]:
root.left = self.constructFromPrePost(pre, post)
else:
l, r = post.index(pre[0]), pre.index(post[-1])
root.left = self.constructFromPrePost(pre[:r], post[:l + 1])
root.right = self.constructFromPrePost(pre[r:], post[l + 1:])
return root
Copy The Code &
Try With Live Editor
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0889_ConstructBinaryTreeFromPreorderAndPostorderTraversal
{
public TreeNode ConstructFromPrePost(int[] pre, int[] post)
{
return ConstructFromPrePost(pre, post, 0, pre.Length - 1, 0, post.Length - 1);
}
private TreeNode ConstructFromPrePost(int[] pre, int[] post, int preLeft, int preRight, int postLeft, int postRight)
{
var length = preRight - preLeft;
if (length < 0) return null;
var root = new TreeNode(pre[preLeft]);
if (length == 0) return root;
var newPostRight = postRight - 1;
while (post[newPostRight] != pre[preLeft + 1])
newPostRight--;
var newLength = newPostRight - postLeft + 1;
root.left = ConstructFromPrePost(pre, post, preLeft + 1, preLeft + newLength, postLeft, newPostRight);
root.right = ConstructFromPrePost(pre, post, preLeft + newLength + 1, preRight, newPostRight + 1, postRight - 1);
return root;
}
}
}
Copy The Code &
Try With Live Editor
Input
Output