This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #105 (Medium): Construct Binary Tree from Preorder and Inorder Traversal
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given two integer arrays
preorderandinorderwherepreorderis the preorder traversal of a binary tree andinorderis the inorder traversal of the same tree, construct and return the binary tree.
Examples:
Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Visual:
Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1]
Constraints:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorderandinorderconsist of unique values.- Each value of
inorderalso appears inpreorder.preorderis guaranteed to be the preorder traversal of the tree.inorderis guaranteed to be the inorder traversal of the tree.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
For this solution, we can take advantage of the order of nodes in the preorder and inorder traversals. A preorder traversal is [node, left, right] while an inorder traversal is [left, node, right].
We know that the root node for a tree is the first element of the preorder array (P). We also know that every element to the left of the root element in the inorder array (I) is on the left subtree, and everything to the right of the root element in I is on the right subtree.
Since we know the length of the left and right subtrees by finding the root in I, and since we know the order of the left and right subtrees in P, we can use that to determine the location of the root node in P for each of the two subtrees.
With this information, we can define a recursive helper function (splitTree) that will split the tree into two and then recursively do the same for each subtree.
In order to make this work, we just need to pass left and right limits (ileft, iright) defining the subarray of the current subtree in I, as well as the index (pix) of the root node of the subtree in P.
At this point, we could iterate forward through I until we found out the location (imid) of the root node each time, but that would push this solution to a time complexity of O(N^2).
Instead, we can make a prelimanary index map (M) of the values in I, so that we can look up the value for imid in O(1) time in each recursion. This will lower the time complexity to O(N) at the cost of a space complexity of O(N).
In the example in the graphic above, where P = [8,2,7,1,9,3,6] and I = [7,2,1,8,3,9,6], the root would be 8, so we know that imid (its location in I) is 3, and since we still are using the full array, ileft = 0 and iright = I.length-1, or 6. This means that the left subtree is imid - ileft = 3 elements long ([7,2,1] to the left of 8 in I) and the right subtree is iright - imid = 3 elements long ([3,9,6] to the right of 8 in I).
We can apply those dimensions from I to figure out the ranges of those subtrees in P, as well. The left subtree will start right after the root in P (pix + 1), and the right subtree will start once the left subtree ends (pix + 1 + (imid - ileft).
At each recursion, if imid = ileft, then there are no nodes in the left subtree, so we shouldn't call a recursion for that side. The same applies to the right side if imid = iright.
- Time Complexity: O(N) where N is the length of P and I
- Space Complexity: O(N) for M
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var buildTree = function(P, I) {
let M = new Map()
for (let i = 0; i < I.length; i++)
M.set(I[i], i)
return splitTree(P, I, M, 0, 0, I.length-1)
};
var splitTree = function(P, I, M, pix, ileft, iright) {
let rval = P[pix],
root = new TreeNode(rval),
imid = M.get(rval)
if (imid > ileft)
root.left = splitTree(P, I, M, pix+1, ileft, imid-1)
if (imid < iright)
root.right = splitTree(P, I, M, pix+imid-ileft+1, imid+1, iright)
return root
}
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def buildTree(self, P: List[int], I: List[int]) -> TreeNode:
M = {I[i]: i for i in range(len(I))}
return self.splitTree(P, I, M, 0, 0, len(P)-1)
def splitTree(self, P: List[int], I: List[int], M: dict, pix: int, ileft: int, iright: int) -> TreeNode:
rval = P[pix]
root, imid = TreeNode(rval), M[rval]
if imid > ileft:
root.left = self.splitTree(P, I, M, pix+1, ileft, imid-1)
if imid < iright:
root.right = self.splitTree(P, I, M, pix+imid-ileft+1, imid+1, iright)
return root
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public TreeNode buildTree(int[] P, int[] I) {
Map<Integer, Integer> M = new HashMap<>();
for (int i = 0; i < I.length; i++)
M.put(I[i], i);
return splitTree(P, I, M, 0, 0, I.length-1);
}
private TreeNode splitTree(int[] P, int[] I, Map<Integer, Integer> M, int pix, int ileft, int iright) {
int rval = P[pix], imid = M.get(rval);
TreeNode root = new TreeNode(rval);
if (imid > ileft)
root.left = splitTree(P, I, M, pix+1, ileft, imid-1);
if (imid < iright)
root.right = splitTree(P, I, M, pix+imid-ileft+1, imid+1, iright);
return root;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
TreeNode* buildTree(vector<int>& P, vector<int>& I) {
unordered_map<int, int> M;
for (int i = 0; i < I.size(); i++)
M[I[i]] = i;
return splitTree(P, I, M, 0, 0, I.size()-1);
}
private:
TreeNode* splitTree(vector<int>& P, vector<int>& I, unordered_map<int, int>& M, int pix, int ileft, int iright) {
int rval = P[pix], imid = M[rval];
TreeNode* root = new TreeNode(rval);
if (imid > ileft)
root->left = splitTree(P, I, M, pix+1, ileft, imid-1);
if (imid < iright)
root->right = splitTree(P, I, M, pix+imid-ileft+1, imid+1, iright);
return root;
}
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-06-08T17:28:35+00:00) Solution: Construct Binary Tree from Preorder and Inorder Traversal. Retrieved from https://www.scien.cx/2021/06/08/solution-construct-binary-tree-from-preorder-and-inorder-traversal/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.