이런모양의 자식노드를 두개씩 가지는 트리가 있는데(노드의 갯수는 1이상 210,000이하)
문제가 두 노드간의 거리를 구하는건데요..
만약에 5 3 이렇게 입력을하면 3이출력되고
4 5 입력하면 2가 출력이되야합니다.
구글링해도 나오질 않네요 도와주세요 ㅠㅠ..
이런모양의 자식노드를 두개씩 가지는 트리가 있는데(노드의 갯수는 1이상 210,000이하)
문제가 두 노드간의 거리를 구하는건데요..
만약에 5 3 이렇게 입력을하면 3이출력되고
4 5 입력하면 2가 출력이되야합니다.
구글링해도 나오질 않네요 도와주세요 ㅠㅠ..
두 값을 a b 반환값을 r이라하고 a b중 큰 걸 2로 나누고 r을 1늘림 a b가 같으면 r반환 아니면 a' b' r'로 재귀
이정돈 직접 짭시다
O(log(N))만에 짜야 한다면 간단하게는
5에서 루트까지 하면 {5,2,1} , 3에서 루트까지 한다면 {3,1} 이므로 둘의 겹치는 부분을 제외하면 {5,2} ,{3}이므로 얘내 둘 더하면 3
http://lgstar.tk
커뮤니티 사이트 입니다 많은 이용 부탁 드립니다. - DCW