Reference: LeetCode 105, LeetCode 106 EPI 9.11

Difficulty: Medium

## Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

**Note:**

**Example:**

1 | preorder = [3,9,20,15,7] |

Return the following binary tree:

1 | 3 |

## Analysis

**Methods:**

Recursion

`Find Root`

: The node of`preorder`

sequence from left to right is always the root of the current subtree.`Split Subtree Nodes`

: According to the root, we can split nodes in the inorder array into two parts belonging to left and right subtrees.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36public TreeNode buildTree(int[] preorder, int[] inorder) {

if (preorder == null || inorder == null) {

return null;

}

// preorder list

LinkedList<Integer> preList = new LinkedList<>();

for (int p : preorder) {

preList.add(p);

}

return build(preList, inorder, 0, inorder.length - 1);

}

private TreeNode build(LinkedList<Integer> preList, int[] inorder, int lo, int hi) {

if (lo > hi) {

return null;

// Don't write "if (lo == hi)", since you forget to do preList.removeFirst()

}

// get the root

int rootVal = preList.removeFirst();

TreeNode root = new TreeNode(rootVal);

int rootIdx = getRootIdx(inorder, rootVal, lo, hi); // O(N)

// left & right

root.left = build(preList, inorder, lo, rootIdx - 1);

root.right = build(preList, inorder, rootIdx + 1, hi);

return root;

}

private int getRootIdx(int[] inorder, int rootVal, int lo, int hi) {

for (int i = lo; i <= hi; ++i) {

if (inorder[i] == rootVal) {

return i;

}

}

return -1;

}**Time:**$O(N\log{N})$ in the best case, and $O(N^2)$ in the worst case, since at each level it takes $O(N)$ to find the root index.**Space:**$O(h)$

Recursion (HashMap)

- Use a
`HashMap`

to map the values to indices.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30public TreeNode buildTree(int[] preorder, int[] inorder) {

if (preorder == null || inorder == null) {

return null;

}

// preorder list

LinkedList<Integer> preList = new LinkedList<>();

for (int p : preorder) {

preList.add(p);

}

// inoder mapping (val -> index)

Map<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < inorder.length; ++i) {

map.put(inorder[i], i);

}

return build(preList, inorder, 0, inorder.length - 1, map);

}

private TreeNode build(LinkedList<Integer> preList, int[] inorder, int lo, int hi, Map<Integer, Integer> map) {

if (lo > hi) {

return null;

}

// get the root

int rootVal = preList.removeFirst();

TreeNode root = new TreeNode(rootVal);

int rootIdx = map.get(rootVal); // O(1)

// left & right

root.left = build(preList, inorder, lo, rootIdx - 1, map);

root.right = build(preList, inorder, rootIdx + 1, hi, map);

return root;

}**Time:**$O(N)$**Space:**$O(N)$

- Use a

Here is the version of `Postorder + Inorder`

:

1 | public TreeNode buildTree(int[] inorder, int[] postorder) { |