이진 트리에서 노드 깊이를 찾지 못함

이진 트리가 bst가 아니므로 해당 이진 트리에서 노드의 깊이를 찾아야합니다. 일부 dilimeter를 사용하여 레벨 순회 이외의 다른 방법을 얻을 수있는 다른 방법이 있습니까? 레벨 카운트를 메인으로한다.이진 트리에서 노드 깊이를 찾지 못함

입력으로 나는 트리의 루트 노드와 트리의 노드 중 하나에 깊이를 찾아야합니다.

나는 당신이 DFS을 할 수있는 BFS 싶지 않아 (그리고 당신은 또한 재귀 적으로 그것을 할 수있는) 경우,이

출처

2011-11-23 Ashish Sharma

숙제에 대한 질문이 있으십니까? –

을 찾기 위해 재귀 적 방법을 갖고 싶어.

출처

2011-11-23 18:40:47

u는 재귀를 사용하여이 코드를 찾을 수 있습니다 .. –

질문이 숙제 문제 인 것처럼 보이므로 마음에 드는 검색 엔진에서 DFS의 작동 방식을 살펴 보시기 바랍니다. –

트리는 BST가 아니기 때문에 최악의 복잡성은 O (n)입니다. 따라서 모든 종류의 탐색 (사전, 사후, 내부)은 현재 노드와 입력 노드를 계속 비교하는 데 도움이됩니다. 이러한 모든 탐색은 재귀를 사용합니다. –

재귀 함수에 추가 매개 변수를 전달하여 깊이를 표시해보십시오.

출처

2011-11-24 07:33:54 kaustubh

추가 매개 변수가 필요하지 않으므로 함수의 반환 값을 간단히 사용할 수 있습니다. –

DFS 기능 용 의사 코드의 경우 첫 번째 호출은 DFS(root)이됩니다.

DFS(node v, integer d) 
    visited[v] = true 
    depth[v] = d 

    for each u such that u is adjacent to v 
    if visited[u] == false 
     DFS(u, d+1)

출처

2011-11-24 10:08:33

visited (acyclic) 또는 depth 변수가 필요하지 않습니다 (하나의 값만 찾고 있기 때문에 모든 노드를 거칠 필요가 없습니다). –

이진 트리에서 노드 깊이를 찾지 못함

답변

관련 문제