java-algorithm-interview/src/ch14/P59_2.java at main · onlybooks/java-algorithm-interview · GitHub

40 lines (31 loc) · 1.4 KB

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);

}

Expand file tree