LeetCode: 106번 (Construct Binary Tree from Inorder and Postorder Traversal) [JAVA]

문제 링크

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

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

풀이

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

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

 앞서 해결한 105번(Construct Binary Tree from Preorder and Inorder Traversal)문제와 매우 유사한 문제이다. 주어진 배열 중 preorder 배열이 postorder 배열로 바뀐게 다이기 때문에, 이에 맞춰서 로직을 수정해주면 된다.
 앞선 105번에서는 preorder 배열을 통해 앞에서 순서대로 접근하며 서브트리의 부모노드를 알아갔지만, postorder는 LRV 순서이기 때문에 서브트리의 부모노드를 뒤에서 앞으로 가며 접근해야 한다. 이 때문에 전체적인 로직의 전개 순서가 V -> L -> R이 아닌, LRV를 뒤집은 V -> R -> L 형태가 되어야 한다.
 이 때문에 세부로직이 변경되는데, 현재 서브트리의 부모노드를 알아내고 inorder 구간에서 해당 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 알아낸 다음, postorderIndex를 -1을 해주어야 한다. 이는 postorder 배열 자체를 뒤에서 앞으로 접근하기 때문이다. 그 다음에는 왼쪽과 오른쪽 서브트리 구성을 위해 재귀함수를 호출해야 하는데, 이 상황에서도 V -> R -> L 순서를 맞추기 위해 오른쪽 서브트리 구성을 위한 재귀함수를 먼저 호출해주고 그 다음 왼쪽 서브트리 구성을 위한 재귀함수를 호출해 현재 부모노드의 오른쪽, 왼쪽에 저장하면 된다.
 해당 부분만을 유의하여 재귀함수를 구성한 다음, 동일하게 주어진 inorder와 postorder 함수를 바탕으로 재귀함수를 호출한 결과값을 반환하면 된다.

 

class Solution {
    int postorderIndex;

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

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

        TreeNode node = new TreeNode(postorder[postorderIndex]);

        for (int i = inorderStart; i <= inorderEnd; i++) {
            if (postorder[postorderIndex] == inorder[i]) {//주어진 inorder 서브트리 구역 중 현재 노드의 위치를 확인
                --postorderIndex;

                node.right = makeSubTree(inorder, postorder, i + 1, inorderEnd);//오른쪽 서브트리 구간을 바탕으로 트리 생성
                node.left = makeSubTree(inorder, postorder, inorderStart, i - 1);//왼쪽 서브트리 구간을 바탕으로 트리 생성

                break;
            }
        }

        return node;
    }
}

결과