백준 22856. 트리 순회

tose33 2024. 3. 20. 14:23

22856번: 트리 순회

노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다.

www.acmicpc.net

1. 우선 중위 순회를 해서 마지막 노드를 찾는다.

방문한 노드를 기록하고 방문하지 않는 노드를 첫 방문했을때 cnt 를 증가시키고,

어떤 노드를 방문했을때 N-1 개의 노드를 이미 방문했다면 그 노드가 마지막 노드다.

2. 이제 문제에서 요구하는대로, 중위 순회 하면서 방문하는 노드의 갯수를 카운트하면 된다.

주의할점은 이전에 구한 마지막 노드에 도달한 후에는 더이상 카운트를 증가시키면 안된다.