다시 정렬 트리를 사용하여 라벨

Question

항상 0

내가 별도의 트리를 구성 할 레이블 루트 노드와 노드 N을 통해 0을 표시하는 나무 (정렬되지 않은)를 고려하는 각 비의 부모 - 루트 노드 m은 레이블이 m보다 작은 가장 가까운 조상입니다.

필요한 출력은 다음과 같습니다 :이 나무 주어진 예를 들어

, 그것은 이동 있도록 노드 2, 상위 5보다 적은 라벨을 가지고

공지 사항 나무 위로; 노드 4는 부모 7 및 조부모 5보다 적으므로 트리를 그 위대한 할아버지 0으로 이동합니다.

순진한 방법은 각 노드를 독립적으로 처리하여 낮은 레이블이 나타날 때까지 위쪽으로 이동하는 것입니다. 이 같은 상황에 매우 비싼된다 : 그것은 같은 느낌

이러한 재 배열 처리를위한 매우 간단 하위 차 알고리즘이 있어야한다, 그러나 나는 찾을도 바로 칵테일을 수립 또는 수 없습니다 중복 프로세싱의 양을 최소화하기위한 확실한 트래버 설 순서. 이것이 잘 정의 된 솔루션의 일반적인 문제입니까?

Answer 1

알고리즘이 다음에 해당합니다

1. 트리의 루트로 0을 설정
2. 원래 나무에 DFS를 수행합니다.
3. 재귀 주입을 수행하십시오.

재귀 분사 (노드 부모)

1. 부모보다 큰 노드는 부모의 자식으로 주입하는 경우.
2. 그렇지 않은 경우 재귀 주입 (node, parent.parent)