Problem:
Construct Binary Tree From Inorder and Preorder/Postorder Traversal
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]
Solution:
Construct Binary Tree From Inorder and Preorder traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
private Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
private int index=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
// build hashmap with inorder indexes
for(int i=0; i<inorder.length; i++) {
inorderMap.put(inorder[i],i);
}
return inorderPreorderTree(inorder, preorder, 0, preorder.length-1);
}
private TreeNode inorderPreorderTree(int[] inorder, int[] preorder, int left, int right { if(left > right) {
return null;
}
int rootVal = preorder[index++];
TreeNode root = new TreeNode(rootVal);
root.left = inorderPreorderTree(inorder, preorder, left, inorderMap.get(rootVal)-1);
root.right = inorderPreorderTree(inorder, preorder, inorderMap.get(rootVal)+1, right);
return root;
}
}
|
Construct a binary from given inorder and postorder traversal
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]
2
3
4
5
6
7
8
9
10
|
class Solution {
private Map<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
private int index;
public TreeNode buildTree(int[] inorder, int[] postorder) {
index = postorder.length-1;
// build hashmap with inorder indexes
for(int i=0; i<inorder.length; i++) {
inorderMap.put(inorder[i],i);
}
return inorderPostorderTree(inorder, postorder, 0, postorder.length-1);
}
private TreeNode inorderPostorderTree(int[] inorder, int[] postorder, int left, int right ) {
if(left > right) {
return null;
}
int rootVal = postorder[index--];
TreeNode root = new TreeNode(rootVal);
root.right = inorderPostorderTree(inorder, postorder, inorderMap.get(rootVal)+1, right);
root.left = inorderPostorderTree(inorder, postorder, left, inorderMap.get(rootVal)-1);
return root;
}
}
|
Click here for more Programming Interview Questions
No comments:
Post a Comment