[대학교이상] Binary tree와 Dyck path 사이의 bijection 찾기

[익명(110.76)]

n vertices Rooted binary tree랑 Dyck path on (0,2n)이랑 개수가 카탈랑 수로 같으니까 bijection 존재할것같고 실제로 존재한다는데 이거 못찾겠다

어떻게 대응시켜야 할지 아이디어좀 주세요..

- dc official App

[익명(211.36)]

이거 rooted tree에서 트리 dfs 돌면서 첫 방문때 0 자식 방문 다 끝나면 1 붙이는 식으로 길이 2n짜리 문자열 만들 수 있는데 그러면 무조건 0이 1보다 같거나 많이 나오다가 마지막엔 01개수가 같아져야해서 dyck path됨 - dc App

[익명(143.248)]

root에서 시작해서 left subtree부터 오른쪽으로 돌리면 됨? - dc App