FilesExpand file tree

 master

/

LeetCode105.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (32 loc) · 1.11 KB

 master

/

LeetCode105.java

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (32 loc) · 1.11 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

36

37

package LeetCode.array;

import java.util.HashMap;

import java.util.Map;

/**

* 前序+中序 恢复成树

*/

public class LeetCode105 {

class TreeNode{

TreeNode left;

TreeNode right;

int val;

public TreeNode(int val) {

this.val = val;

}

}

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

if(preorder == null || inorder == null) return null;

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

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

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

}

return preIn(map, preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);

}

private TreeNode preIn(Map<Integer, Integer> map, int[] preorder, int pi, int pj, int[] in, int ni, int nj){

if(pi > pj) return null;

int index = map.get(preorder[pi]);

TreeNode node = new TreeNode(preorder[pi]);

node.left = preIn(map, preorder, pi+1, pi+index-ni, in, ni, index-1);

node.right = preIn(map, preorder, pi+index-ni+1, pj, in, index+1, nj);

return node;

}

}