❒ Description
날짜 | 2024.09.26 (목) |
레벨 | Medium |
제목 | Construct BT from Preorder and Inorder Traversal |
링크 | https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/ |
자료구조 | 그래프 - BST |
시간 복잡도 | O(n) |
❒ 문제 및 로직 분석
int[] preorder = {1, 2, 4, 5, 3, 6, 7, 9, 8}; // 전위 순회
int[] inorder = {4, 2, 5, 1, 7, 9, 6, 8, 3}; // 중위 순회
전위 순회의 첫 번째 값은 항상 root 노드다. 즉, 전위 순회의 첫 번째 결과는 정확히 중위 순회 결과를
왼쪽과 오른쪽을 분할하는 역할을 한다. 이렇게 하면 이 문제를 Divide and Conquer(분할정복) 문제로
바라볼 수 있다.
정리하자면 전위 순회에서는 root 노드를 선별하고, 이렇게 선별한 root 노드를 중위 순회에서 찾는다.
그리고 root 노드를 기준으로 중위 순회를 Left와 Right로 분할한다.
위 그림에서 1을 기준으로 [ 4, 2, 5 ]는 왼쪽 서브트리에 속하고 [ 7, 9, 6, 8, 3 ]은 오른쪽 서브트리에 속하게 된다.
왼쪽 서브트리를 처리하기 위해서는 pre-order를 왼쪽 부터 순차적으로 탐색하면 된다. 하지만 오른쪽 서브트리를
차리하기 위해서는 위 그림의 빨간 박스를 3으로 옮겨줘야 한다.
아래 식은 오른쪽 서브트리를 처리하기 위해 전위 순회에서 어디서부터 시작해야 하는지 계산하는 식이다.
preIndex + inIndex - inStart
- preIndex : 현재 서브트리의 루트 노드를 가리키는 전위 순회의 인덱스
- inIndex : 중위 순회에서 현재 루트 노드의 인덱스
- inStart : 중위 순회의 현재 서브트리의 시작점
위 식에 각 값을 대입하면 오른쪽 서브트리의 root 노트는 preorder[4] = 3 이 된다.
❒ Solution
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 재귀 DFS 진행. 초깃값은 전위 순회 인덱스 = 0, 중위 순회 인덱스 시작 = 0, 종료 = 길이 - 1
return dfs(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode dfs(int preIndex, int inStart, int inEnd, int[] preorder, int[] inorder) {
// 예외 처리
if (preIndex > preorder.length - 1 || inStart > inEnd) {
return null;
}
// 전위 순회 값이 중위 순회에서는 몇 번째 인덱스인지 추출
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == preorder[preIndex]) {
inIndex = i;
}
}
// 해당 인덱스는 중위 순회를 분할하는 노드로 지정
TreeNode node = new TreeNode(inorder[inIndex]);
// 전위순회 다음 결과를 보도록 인덱스 + 1
preIndex ++;
// 왼쪽 자식 노드부터 진행
node.left = dfs(preIndex, inStart, inIndex - 1, preorder, inorder);
// 나머지 값으로 오른쪽 자식 노드 진행
node.right = dfs(preIndex + inIndex - inStart, inIndex + 1, inEnd, preorder, inorder);
return node;
}
'Algorithm > 문제풀이' 카테고리의 다른 글
[LeetCode#783] Minimum Distance Between BST Nodes (0) | 2024.09.25 |
---|---|
[LeetCode#938] Range Sum of BST (0) | 2024.09.25 |
[LeetCode#1038] Binary Search Tree to Greater Sum Tree (0) | 2024.09.25 |
[LeetCode#108] Convert Sorted Array to Binary Search Tree (0) | 2024.09.25 |
[LeetCode#310] Minimum Height Trees (0) | 2024.09.24 |