In this post, we are going to solve the 105. Construct Binary Tree from Preorder and Inorder Traversal problem of Leetcode. This problem 105. Construct Binary Tree from Preorder and Inorder Traversal is a Leetcode medium level problem. Let’s see code, 105. Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solution.
Problem
Given two integer arrays preorder
and inorder
where preorder
is the preorder traversal of a binary tree and inorder
is the inorder traversal of the same tree, construct and return the binary tree.
Example 1 :
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2 :
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Constraints
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder
andinorder
consist of unique values.- Each value of
inorder
also appears inpreorder
. preorder
is guaranteed to be the preorder traversal of the tree.inorder
is guaranteed to be the inorder traversal of the tree.
Now, let’s see the code of 105. Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solution.
Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solution
105. Construct Binary Tree from Preorder and Inorder Traversal – Solution in Java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode buildTree(int[] inorder, int[] preorder, int psi,int pei, int isi, int iei){ if(isi > iei) return null; int idx = isi; while(preorder[psi] != inorder[idx]) idx++; int dist = idx - isi; TreeNode node = new TreeNode(preorder[psi]); node.left = buildTree(inorder,preorder,psi+1,psi+dist,isi,idx-1); node.right = buildTree(inorder,preorder,psi+dist+1,pei,idx+1,iei); return node; } public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; return buildTree(inorder,preorder,0,n-1,0,n-1); } }
105. Construct Binary Tree from Preorder and Inorder Traversal – Solution in C++
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int preInd=0; map<int, int > mp; TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) { for(int i = 0 ; i <inorder.size(); i++) mp[inorder[i]] = i; return createTree(preorder,inorder,0,inorder.size() - 1); } TreeNode* createTree(vector<int>& preorder, vector<int>& inorder,int start, int end){ if(start > end) return NULL; TreeNode* node=new TreeNode(preorder[preInd++]); int pos = mp[node->val]; node->left =createTree(preorder, inorder,start,pos-1); node->right =createTree(preorder, inorder, pos+1,end); return node; } };
105. Construct Binary Tree from Preorder and Inorder Traversal – Solution in Python
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def buildTree(self, preorder, inorder): if not preorder and not inorder: return None if len(preorder) == 1: return TreeNode(preorder[0]) idx = inorder.index(preorder[0]) root = TreeNode(preorder[0]) root.left = self.buildTree(preorder[1:1+idx], inorder[:idx]) root.right = self.buildTree(preorder[1+idx:], inorder[idx+1:]) return root
Note: This problem 105. Construct Binary Tree from Preorder and Inorder Traversal is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.