221. Construct a BT from Postorder and Inorder

Given two integer arrays Postorder and Inorder. Where Postorder is the postorder traversal of a binary tree and Inorder is the inorder traversal of the same tree.

Construct and return the binary tree using the postorder and inorder arrays.

Example 1:

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

Output : [3, 9, 20, null, null, 15, 7]

Explanation : The output tree is shown below.

Example 2:

Input : postorder = [5, 6, 4, 9, 2, 3] , inorder = [5, 4, 6, 3, 2, 9]

Output : [3, 4, 2, 5, 6, null, 9]

Explanation : The output tree is shown below.

Now Your Turn!

Pick the correct output for the given input

Input : postorder = [6, 8, 1, 4, 7, 2, 5], inorder = [8, 6, 1, 5, 4, 2, 7]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= Number of Nodes <= 3000
  • -104 <= Node.val <= 104
  • All values in the given tree are unique.
  • Each value of inorder also appears in postorder.
  • Postorder is guaranteed to be the postorder traversal of the tree.
  • Inorder is guaranteed to be the inorder traversal of the tree.

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
//your code goes here
}
};
Test Case

Input:

Inorder
Postorder
to save your code