MrainW's Home

All things come to those who wait!

0%

LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Question

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:

1
2
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

1
2
Input: preorder = [-1], inorder = [-1]
Output: [-1]

Solution

  • Solution1 – preorder traversal, inorder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
int[] preorder;
int[] inorder;
int preOrderIndex;
Map<Integer, Integer> treeMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
this.preOrderIndex = 0;
int N = preorder.length;
for (int i = 0; i < N; i++) treeMap.put(inorder[i], i);
return helperbulid(0, N-1);
}
public TreeNode helperbulid(int instart, int inend){
if(instart > inend) return null;
TreeNode root = new TreeNode(preorder[preOrderIndex++]);
int index = treeMap.get(root.val);
root.left = helperbulid(instart, index - 1);
root.right = helperbulid(index + 1, inend);
return root;
}
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Welcome to my other publishing channels