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
andpostorder
consist of unique values.- Each value of
postorder
also appears ininorder
. 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