[LeetCode#105]Construct BT from Preorder and Inorder Traversal

 

❒ 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로 분할한다. 

Divide and Conquer

위 그림에서 1을 기준으로 [ 4, 2, 5 ]는 왼쪽 서브트리에 속하고 [ 7, 9, 6, 8, 3 ]은 오른쪽 서브트리에 속하게 된다.

왼쪽 서브트리를 처리하기 위해서는 pre-order를 왼쪽 부터 순차적으로 탐색하면 된다. 하지만 오른쪽 서브트리를

차리하기 위해서는 위 그림의 빨간 박스를 3으로 옮겨줘야 한다.

 

그럼 어떻게 오른쪽 서브트리를 처리하는 분석해보자. 먼저 오른쪽 서브트리의 루트 노드가 어디에 있는지 계산해야

한다. 아래 식은 오른쪽 서브트리를 처리하기 루트 노드를 찾는 식이다.

preIndex + inIndex - inStart

• preIndex : 현재 서브트리의 루트 노드를 가리키는 전위 순회의 인덱스
• inIndex : 중위 순회에서 현재 루트 노드의 인덱스
• inStart : 중위 순회의 현재 서브트리의 시작점

왜 이런식이 나올까?

이 식은 전위 순회의 특성을 반영한 것이다. 전위 순회는 Root > Left > Right 순으로 노드를 순회한다.

따라서 왼쪽 서브트리의 모든 노드 수만큼 전위 순회의 인덱스를 이동해야 한다.

여기서 `inIndex - inStart` 는 왼쪽 서브트리의 노드 수를 의미한다. 이 만큼을 preIndex에 더해주면,

오른쪽 서브트리의 첫 번째 노드로 이동할 수 있다.

위 식에 각 값을 대입하면 오른쪽 서브트리의 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;
}

 

 

 

 

 

---