FilesExpand file tree

 main

/

P59_2.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

40 lines (31 loc) · 1.4 KB

 main

/

P59_2.java

Top

File metadata and controls

• Code
• Blame

40 lines (31 loc) · 1.4 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

38

39

40

package ch14;

import datatype.TreeNode;

import java.util.ArrayList;

import java.util.List;

public class P59_2 {

public TreeNode dfs(List<Integer> preOrder, List<Integer> inOrder) {

// 예외 처리

if (inOrder.isEmpty()) return null;

// 전위 순회 값이 중위 순회에서는 몇 번째 인덱스인지 추출

int inIndex = inOrder.indexOf(preOrder.get(0));

// 해당 인덱스는 중위 순회를 분할하는 노드로 지정

TreeNode node = new TreeNode(inOrder.get(inIndex));

// 왼쪽 자식 노드부터 진행

node.left = dfs(preOrder.subList(1, inIndex + 1), inOrder.subList(0, inIndex));

// 오른쪽 자식 노드 진행

node.right = dfs(preOrder.subList(inIndex + 1, preOrder.size()), inOrder.subList(inIndex + 1, inOrder.size()));

return node;

}

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

// 원시형을 참조형으로 처리하기 위해 변수 선언

List<Integer> preOrder = new ArrayList<>();

List<Integer> inOrder = new ArrayList<>();

// 정수형 배열을 리스트에 삽입하여 변환

for (int pre : preorder)

preOrder.add(pre);

for (int in : inorder)

inOrder.add(in);

// 재귀 DFS 진행, 리스트로 처리하면 파라미터가 간결해진다.

return dfs(preOrder, inOrder);

}

}