백준 '2236번: 트리의 순회' 문제를 처음 접하고 중위 순회 경로를 활용하여 트리를 재구축한다면 문제를 쉽게 풀 수 있을 것이라 생각했다. 그러나 중위 순회 경로만으로 트리를 재구축하기에는 치명적인 문제가 있었다.

중위 순회 경로의 함정

---

• 포화 이진 트리의 중위 순회 경로가 아니라면 중위 순회 경로의 중간 노드 값이 root 노드를 대표하지 않는다.
• 아래의 예시 case들 처럼 노드의 수가 짝수일 때 root 노드를 특정할 수 없고 설령 짝수라 해도 트리가 치우쳐져 있다면 마찬가지로 root 노드를 알 수 없다.

중위 순회와 후위 순회의 특성을 활용한 트리 구조 재구축

---

중위 순회의 특성

• 방문 순서: 왼쪽 서브트리 -> 현재 노드 -> 오른쪽 서브 트리
• root node를 기준으로 왼쪽 sub tree는 왼쪽에 위치하고 오른쪽 sub tree는 오른쪽에 위치

후위 순회의 특성

• 방문 순서: 왼쪽 서브트리 -> 오른쪽 서브 트리 -> 현재 노드
• root node가 항상 맨 마지막에 위치

코드 예시

1. 후위 순회의 특성을 활용하여 root 노드를 찾아낸다.
2. 중위 순회의 특성을 활용하여 root 노드를 기준으로 left sub tree와 right sub tree를 찾는다.
3. 1 ~ 2번의 과정을 반복하며 sub tree를 계속 구축해나간다.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class BinaryTreeReconstruction {
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }
        return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private static TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd,
                                            int[] postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        int inorderIndex = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                inorderIndex = i;
                break;
            }
        }

        int leftSubtreeSize = inorderIndex - inStart;
        root.left = buildTreeHelper(inorder, inStart, inorderIndex - 1,
                                    postorder, postStart, postStart + leftSubtreeSize - 1);
        root.right = buildTreeHelper(inorder, inorderIndex + 1, inEnd,
                                     postorder, postStart + leftSubtreeSize, postEnd - 1);

        return root;
    }

    public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    public static void main(String[] args) {
        int[] inorder = {9, 4, 13, 1, 16, 6, 11, 2, 10, 7, 12, 3, 15, 5, 14};
        int[] postorder = {9, 13, 4, 16, 11, 6, 1, 10, 12, 7, 15, 14, 5, 3, 2};
        TreeNode root = buildTree(inorder, postorder);

        System.out.println("중위 순회 결과로 재구축한 이진 트리:");
        inorderTraversal(root);
    }
}