[ 22856 ] [ Tree ] 트리 순회

https://www.acmicpc.net/problem/22856

22856번: 트리 순회

---

풀이 과정

---

마지막 노드인 7번 노드를 방문하는 경로를 제외하고는 양방향으로 연결되어 있음 

1. Tree를 먼저 중위순회 해보고 마지막에 방문하는 정점이 어디인지 파악한다.
2. 전체 간선의 개수의 두배에서 마지막에 방문하는 정점을 방문하기 위해 지나온 간선의 개수를 빼주어서 출력

---

소스 코드

---

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()
left = dict()
right = dict()

N = int(input())
parent = [0] * (N+1)
node_count = 0
for _ in range(N):
    a, b, c = map(int, input().split())
    left[a] = b
    right[a] = c

    if b != -1:
        parent[b] = a
        node_count += 1
    if c != -1:
        parent[c] = a
        node_count += 1

# 마지막 노드 구하는 파트
last_node = 0
def traverse(node):
    global last_node
    if node == -1:
        return
    traverse(left[node])
    last_node = node
    traverse(right[node])

traverse(1)
edge_count = node_count * 2
movement = 0
# 마지막 노드까지 이동 경로의 거리 구함
while last_node != 1:
    movement += 1
    last_node = parent[last_node]
print(edge_count - movement)