Construct Binary Tree from Inorder and Postorder Traversal  – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.
• inorder is guaranteed to be the inorder traversal of the tree.
• postorder is guaranteed to be the postorder traversal of the tree.

C++  Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution

class Solution {
public:
    TreeNode *Tree(vector<int>& in, int x, int y,vector<int>& po,int a,int b){
        if(x > y || a > b)return nullptr;
        TreeNode *node = new TreeNode(po[b]);
        int SI = x;  
        while(node->val != in[SI])SI++;
        node->left  = Tree(in,x,SI-1,po,a,a+SI-x-1);
        node->right = Tree(in,SI+1,y,po,a+SI-x,b-1);
        return node;
    }
    TreeNode* buildTree(vector<int>& in, vector<int>& po){
        return Tree(in,0,in.size()-1,po,0,po.size()-1);
    }
};

Java  Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution

public TreeNode buildTreePostIn(int[] inorder, int[] postorder) {
	if (inorder == null || postorder == null || inorder.length != postorder.length)
		return null;
	HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>();
	for (int i=0;i<inorder.length;++i)
		hm.put(inorder[i], i);
	return buildTreePostIn(inorder, 0, inorder.length-1, postorder, 0, 
                          postorder.length-1,hm);
}

private TreeNode buildTreePostIn(int[] inorder, int is, int ie, int[] postorder, int ps, int pe, 
                                 HashMap<Integer,Integer> hm){
	if (ps>pe || is>ie) return null;
	TreeNode root = new TreeNode(postorder[pe]);
	int ri = hm.get(postorder[pe]);
	TreeNode leftchild = buildTreePostIn(inorder, is, ri-1, postorder, ps, ps+ri-is-1, hm);
	TreeNode rightchild = buildTreePostIn(inorder,ri+1, ie, postorder, ps+ri-is, pe-1, hm);
	root.left = leftchild;
	root.right = rightchild;
	return root;
}
 

Python 3  Construct Binary Tree from Inorder and Postorder Traversal LeetCode Solution

class Solution:
    def buildTree(self, inorder, postorder):
        map_inorder = {}
        for i, val in enumerate(inorder): map_inorder[val] = i
        def recur(low, high):
            if low > high: return None
            x = TreeNode(postorder.pop())
            mid = map_inorder[x.val]
            x.right = recur(mid+1, high)
            x.left = recur(low, mid-1)
            return x
        return recur(0, len(inorder)-1)

Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1

Leave a comment below

Related posts:

Construct Binary Tree from Preorder and Inorder Traversal – LeetCode Solution Tree: Preorder Traversal – HackerRank Solution Tree: Preorder Traversal – HackerRank Solution Binary Search Tree : Lowest Common Ancestor – HackerRank Solution Insert Interval – LeetCode Solution Remove Duplicates from Sorted Array II – LeetCode Solution