1
   / \
  2   3
 / \
4   5

인오더

왼쪽 서브트리를 인오더 순회한다.
현재 노드(루트)를 방문한다.
오른쪽 서브트리를 인오더 순회한다.

인오더 순회 결과: 4, 2, 5, 1, 3

포스트오더

왼쪽 서브트리를 포스트오더 순회한다.
오른쪽 서브트리를 포스트오더 순회한다.
현재 노드(루트)를 방문한다.

포스트오더 순회 결과: 4, 5, 2, 3, 1

프리오더

현재 노드(루트)를 방문한다.
왼쪽 서브트리를 프리오더 순회한다.
오른쪽 서브트리를 프리오더 순회한다.

프리오더 순회 결과: 1, 2, 4, 5, 3

구현 코드

public class BinaryTreeTraversal {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

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

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

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

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

    public static void main(String[] args) {
        BinaryTreeTraversal tree = new BinaryTreeTraversal();

        // 트리 생성
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        System.out.print("In-order Traversal: ");
        tree.inOrderTraversal(root);
        System.out.println();

        System.out.print("Post-order Traversal: ");
        tree.postOrderTraversal(root);
        System.out.println();

        System.out.print("Pre-order Traversal: ");
        tree.preOrderTraversal(root);
        System.out.println();
    }
}

외우는 법

인오더 : 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서

포스트오더: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

프리오더 : 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

구현팁 : 루트가 언제 출력될 지 위 순서대로 재귀를 구현하면 된다.