트리 dfs 구현 템플릿

클래스 구현

일반 트리

class Node {
    int value;
    List<Node> children = new ArrayList<>();

    Node(int value) {
        this.value = value;
    }
}

void dfs(Node node) {
    // 현재 노드 처리 (예: 값 출력)
    System.out.println(node.value);

    // 자식 노드로 재귀 호출
    for (Node child : node.children) {
        dfs(child);
    }
}

 

이진 트리

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }
}

void dfs(Node node) {
    if (node == null) { // node가 null인 경우
        return;
    }

    System.out.println(node.value); // 현재 노드 처리 (방문)
    dfs(node.left);                 // 왼쪽 자식 방문
    dfs(node.right);                // 오른쪽 자식 방문
}

인접리스트

일방향 트리

Map<Integer, List<Integer>> tree = new HashMap<>() {{
    put(1, List.of(2, 3));
    put(2, List.of(4, 5));
    put(3, List.of());
    put(4, List.of());
    put(5, List.of());
}};

void dfs(int cur):
    for (int nxt : tree.get(cur)) {
        dfs(nxt);
		}
}

 

양방향 트리

Map<Integer, List<Integer>> tree = new HashMap<>() {{
    put(1, List.of(2, 3));
    put(2, List.of(1, 4, 5));
    put(3, List.of(1));
    put(4, List.of(2));
    put(5, List.of(2));
}};

void dfs(int cur, Set<Integer> visited) {
    visited.add(cur);
    for (int nxt : tree.get(cur)) {
        if (!visited.contains(nxt)) {
            dfs(nxt, visited);
        }
    }
}