Algorithm

Problem Name: 889. 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` and `postorder` 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 &

Input

cmd
preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output

cmd
[1,2,3,4,5,6,7]

#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 &

Input

cmd
preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output

cmd
[1,2,3,4,5,6,7]

#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 &

Input

cmd
preorder = [1], postorder = [1]

Output

cmd
[1]

#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 &

Input

cmd
preorder = [1], postorder = [1]

Output

cmd
[1]

#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 &

Input

cmd
preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output

cmd
[1,2,3,4,5,6,7]