LeetCode: 105번 (Construct Binary Tree from Preorder and Inorder Traversal) [JAVA]

문제 링크

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 preorder 배열 속 인덱스를 나타내는 정수(preorderIndex) 초기화
2. 서브트리를 생성하는 재귀함수 구현 (인자는 preorder 배열, inorder 배열, inorder 구간시작 인덱스를 나타내는 inorderStart, inorder 구간끝 인덱스를 나타내는 inorderEnd)
   1) 만약 인자로 들어온 inorderStart 정수가 inorderEnd 보다 크다면, null을 리턴
   2) preorder 배열에서 preorderIndex 순서의 값을 가져와 노드를 생성
   3) inorderStart부터 inorderEnd까지 반복문을 돌며, 해당 구간 속 preorder[preorderIndex] 값과 동일한 위치를 탐색
   4) 이후 위치를 찾았다면 preorderIndex를 +1 해준 다음, 앞서 생성한 노드의 왼쪽과 오른쪽에 동일한 재귀함수를 호출한 결과를 삽입
   5) 이후 해당 노드를 반환
3. 이후 해당 재귀함수를 호출한 결과값을 반환 

 노드를 preorder와 inorder 순회한 배열만으로, 트리를 재구성해야 하는 문제이다. 이 때 preorder를 통해선 전체 트리를 현재 노드 -> 왼쪽 서브 트리 ->  오른쪽 서브 트리(VLR) 순서로 순회하고, inorder의 경우 전체 트리를 왼쪽 서브 트리 -> 현재 노드 -> 오른쪽 서브 트리(LVR)로 순회한다.
 각각의 배열을 통해 얻어낼 수 있는 정보가 다르다. preorder를 통해선, 특정 서브 트리 구역에 대한 부모 노드가 무엇인지를 알 수 있다. 예를 들어 예시로 주어진 트리 사진이 이렇다.

 이 때 주어진 preorder 배열 정보가 [3, 9, 20, 15, 7]인데, 이를 보면 VLR 순서대로 각각의 노드가 특정 서브 트리의 부모 노드란 것을 알 수 있다. 3은 전체 트리의 부모 노드, 9 또한 3의 왼쪽 서브 트리에 대한 부모 노드, 이어 20, 15, 7 또한 모두 특정 서브 트리 구역에 대한 부모 노드들이다. 이처럼 배열의 각 요소를 순차적으로 접근할 때, VLR 순서로 각 서브트리들의 부모노드를 알아낼 수 있다.
 반대로 inorder 배열을 통해선, 서브트리 구역 중 부모 노드를 기준으로 왼쪽 서브트리 구역과 오른쪽 서브트리 구역을 구분 지을 수 있다. 동일한 예시의 inorder 배열 정보가 [9, 3, 15, 20, 7]일 때, 3을 기준으로 볼때 {9}와 {15, 20, 7}이 각각 왼쪽과 오른쪽 서브트리의 구역임을 알 수 있다. 다만 이 때 중요한 점은 초기 서브 트리의 구역이 명확하게 주어진 상태여야 세부 서브 트리 구역을 특정 지을 수 있다는 점이다. 예를 들어 20을 기준으로는 왼쪽과 오른쪽 서브트리 구역이 각각 {15}와 {7}이지만, 배열 상으론 15 앞에 9와 3이 같이 있기 때문에 20으로 탐색할 서브 트리 구역을 명확하게 알아야 한다. 다만 이 문제는, 재귀적으로 트리를 쪼개가며 구역을 나누는 과정으로 해결할 수 있다. 3을 통해 {9}와 {15, 20, 7}로 서브 트리가 나누어진 다는 것을 알았다면, 이후 {15, 20, 7}만을 탐색하여 20을 기준으로 {15}와 {7}로 나눌 수 있기 때문이다.
 앞선 두 정보를 활용하여, 재귀적으로 서브트리를 완성해나가는 방식으로 트리를 구축할 수 있다. 재귀함수의 인자로는 preorder과 inorder 배열, 그리고 inorder 속 서브트리 구간을 나타내는 인덱스 inorderStart와 inorderEnd를 받는다. 서브트리 구역이 있어야 트리를 구성할 수 있기 때문에, 만약 inorderStart>inorderEnd와 같이 탐색할 서브트리 구간이 없다면 null을 반환한다. 그 다음엔 일종의 전역변수처럼 생성된 preorderIndex를 통해 현재 구성할 서브트리 속 부모 노드의 값을 가져와 노드를 생성한다.
 이후엔 inorder 속 서브트리 구간에서 왼쪽 서브트리와 오른쪽 서브트리 구간을 찾아낸다. 반복문을 통해, inorder 구간 속 현재 부모노드와 동일한 값을 가진 인덱스(i)를 찾아낸다. 그리고 여기서 preorderIndex를 +1 해주는데, 이는 트리의 접근 과정이 VLR이기 때문에 순차적으로 노드들을 접근하기 위함이다. 그 다음엔 왼쪽 서브트리 구성과 오른쪽 서브트리의 구성을 동일한 재귀함수로 구성한다. 이때 왼쪽 서브트리 구간이라면 구간이 inorderStart부터 i-1까지, 오른쪽 서브트리 구간이라면 구간이 i+1부터 inorderEnd까지이다. 이를 통해 구현한 결과 노드를 각각 노드의 왼쪽과 오른쪽에 붙이면 된다.
 그렇게 생성이 완료된 트리 노드를 반환하며, 결과적으로 주어진 preorder 배열과 inorder 배열에 대해 해당 재귀함수를 호출한 결과를 반환하면 된다.

 

class Solution {
    int preorderIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return makeSubTree(preorder, inorder, 0, inorder.length - 1);
    }

    public TreeNode makeSubTree(int[] preorder, int[] inorder, int inorderStart, int inorderEnd) {
        if (inorderStart > inorderEnd) {//탐색할 서브트리 구역이 없다면
            return null;
        }

        TreeNode node = new TreeNode(preorder[preorderIndex]);//현 인덱스 기반 노드 생성

        for (int i = inorderStart; i <= inorderEnd; i++) {//전체 서브 트리 구간 중
            if (preorder[preorderIndex] == inorder[i]) {//현재 LVR에서 현재 V를 찾았다면
                ++preorderIndex;

                node.left = makeSubTree(preorder, inorder, inorderStart, i - 1);//L구간에 대해 트리 생성 진행
                node.right = makeSubTree(preorder, inorder, i + 1, inorderEnd);//R구간에 대해 트리 생성 진행

                break;
            }
        }

        return node;
    }
}

결과