LeetCode - 106

106. Construct Binary Tree from Inorder and Postorder Traversal

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

이진 트리의 Inorder과 Postorder 순회 결과가 주어졌을 때, 이진 트리를 구성하는 문제이다.

문제를 해결하기 위해 순회 결과를 분석한 결과, 다음과 같은 사실을 알아냈다.

• Inorder에서 루트 값이 나오기 전은 leftChild, 루트 값 이후는 rightChild
• Postorder의 마지막은 트리의 루트 노드
• Inorder에서 leftChild 개수를 n이라고 했을 때, Postorder에서 0 ~ n-1는 leftChild, n ~ length - 1는 rightChild

위의 사실을 토대로 루트 노드와, 왼쪽/오른쪽 자식을 구분할 수 있다.

루트가 1이라는 사실은 알아냈으니, 다음은 각각의 자식이 어떻게 이루어졌는지 알아내야 한다.

이진 트리의 특성으로 인해, 각각의 자식 역시 이진 트리로 구성되어 있다. 자식 트리들의 순회 결과에 처음 루트 노드과 같은 방식을 적용해보자.

이렇게 자식들을 쪼개다보면, 순회 결과의 값들이 트리의 어느 부분에 위치해야 하는지 쉽게 구할 수 있다.

---

import java.util.stream.IntStream;

class Solution {    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode tree = null;
                
        int length = inorder.length;
        
        if(length == 1) {
            return new TreeNode(inorder[0]);
        } else if(length == 0) {
            return null;
        }
            
        int root = postorder[length - 1];
        
        int rootIndex = IntStream.range(0, length).filter(i -> root == inorder[i]).findFirst().orElse(-1);
        
        tree = new TreeNode(root, buildTree(Arrays.copyOfRange(inorder, 0, rootIndex), Arrays.copyOfRange(postorder, 0, rootIndex)),
                            buildTree(Arrays.copyOfRange(inorder, rootIndex + 1, length), Arrays.copyOfRange(postorder, rootIndex, length - 1)));
        
        return tree;
    }
}

https://leetcode.com/submissions/detail/590525700/
https://github.com/sorious77/LeetCode/blob/main/code/106.java

문제 해결은 했지만, 시간이 너무 오래 걸려 솔루션을 찾아보니 HashMap을 사용하면 시간을 줄일 수 있는거 같다..!!