[leet code] 889. Construct Binary Tree from Preorder and Postorder Traversal (JAVA)

[leet code] 889. Construct Binary Tree from Preorder and Postorder Traversal

🗒️알고리즘 분류

#Binary Tree #Tree #Recursion #preorder #postorder #트리 #이진 트리 #재귀 #전위 순회 #후위 순회

📌기억할 만한 포인트

EX) Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

이진 트리의 전위 순회 순서(int[] preorder), 후위 순회 순서(int[] postorder)를 이용해 이진 트리의 모습을 재구성해서 반환하는 문제이다.

기억할 만한 점은 총 2가지이다.

1. 전위 순회는 (root - left - right)의 순서로 항상 현재 서브 트리의 root 가 먼저 나온다.
   후위 순회는 (left - right - root)의 순서로 항상 왼쪽 서브 트리가 먼저 나온다.
2. 서브 트리의 크기를 구할 때, 후위 순회 순서의 index(postIndexMap) 와 후위 순회의 시작 index(postStart) 를 이용한다. 전위 순회는 항상 현재 서브 트리의 root 가 먼저 나오고, 후위 순회는 왼쪽 서브 트리가 전부 나오고 오른쪽 서브 트리가 나온다.
   따라서, 왼쪽 서브 트리의 root 값이 후위 순회 순서(int[] postorder)의 어느 위치에 오는지 안다면, 그 위치(indexInPostOrder[leftRoot])와 현재 서브트리의 시작 인덱스(postStart)의 차이를 통해 왼쪽 서브트리에 속한 노드의 개수를 정확하게 구할 수 있다.

오랜만에 대학교 알고리즘 시간에 배웠던 이진 트리의 원리를 다시 상기시킨 좋은 문제였다.

📝풀이 코드(JAVA)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private static Map<Integer, Integer> postIndexMap;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        postIndexMap = new HashMap<>();

        for (int i = 0; i < postorder.length; ++i) {
            postIndexMap.put(postorder[i], i);
        }    

        return construct(0, preorder.length-1, 0, preorder);
    }

    private TreeNode construct(int preStart, int preEnd, int postStart, int[] preorder) {
        if (preStart > preEnd) {
            return null;
        }
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }

        TreeNode root = new TreeNode(preorder[preStart]);

        int leftRoot = preorder[preStart+1];
        int index = postIndexMap.get(leftRoot);
        int leftSubTreeSize = index - postStart + 1;

        root.left = construct(preStart + 1, preStart + leftSubTreeSize, postStart, preorder);
        root.right = construct(preStart + leftSubTreeSize + 1, preEnd, postStart + leftSubTreeSize, preorder);

        return root;
    }
}

⏰총 풀이시간

• 120분;;