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 <= 301 <= preorder[i] <= preorder.length- All the values of
preorderare unique. postorder.length == preorder.length1 <= postorder[i] <= postorder.length- All the values of
postorderare unique. - It is guaranteed that
preorderandpostorderare 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;
}
};
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;
}
}
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
})()
}
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
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;
}
}
}
Input
Output