최대 M개의 연속 노드와 값 K를 갖는 루트에서 리프까지의 경로 수

소개

이진 트리는 컴퓨터 과학 및 프로그래밍 분야에 폭넓게 응용되는 매혹적인 데이터 구조입니다. 흥미로운 문제는 부모 노드와 그 자식 노드로 구성된 주어진 트리에서 개수를 찾는 것입니다. 이진 트리는 노드로 구성되며 루트 노드가 결정되며 루트 노드는 사용자 요구에 따라 자식 노드를 제공할 수 있습니다. K 값이 결정되고, M 값에 따라 이동 방식이 선택됩니다.

루트에서 리프까지의 경로 수

그래프는 정수 형태의 값을 보유하는 다양한 노드를 사용하여 생성됩니다. 이 기사에서는 주로 시작 노드 또는 루트 노드에서 리프 노드 또는 하위 노드까지 계산하는 데 중점을 둡니다.

예

그래프는 다양한 노드가 있는 이진 트리에서 생성됩니다.

• 위 이진 트리에서 루트 노드는 "8"로 선택되었습니다.

• 그런 다음 두 개의 노드를 만듭니다. 하나는 값이 3이고 다른 하나는 값이 10이며 루트 노드의 왼쪽과 오른쪽 위치를 차지합니다.

• 값이 2인 노드를 루트로 가져와 각각 왼쪽 및 오른쪽 노드로 값 2와 1을 갖는 또 다른 하위 노드를 만듭니다.

• 마지막으로 값이 1인 하위 노드는 값이 -4인 하위 노드를 생성합니다.

방법 1: 재귀 함수를 사용하여 K 값을 갖는 최대 M개의 연속 노드로 구성된 루트-리프 경로를 계산하는 C++ 코드

이 문제를 효율적으로 해결하기 위해 트리 순회 알고리즘 및 재귀와 같은 기본 개념을 활용하겠습니다.

알고리즘

1단계: 두 개의 포인터(왼쪽 하위 노드와 오른쪽 하위 노드)와 노드 값을 저장하는 정수 필드를 포함하는 트리 노드를 나타내는 구조를 만듭니다.

2단계: 현재 경로 길이(0으로 초기화됨), 연속 발생 횟수(초기 0으로 설정됨), 목표 값 K 및 연속 발생의 최대 허용 수 M .

3단계: 각 왼쪽 및 오른쪽 하위 트리에서 함수를 재귀적으로 호출하여 증분 경로 길이 및 연속 발생 횟수(해당하는 경우)와 같은 업데이트된 매개변수를 전달합니다.

4단계: 순회 중에 방문한 비어 있지 않은 각 노드에 대해:

a) 값이 K와 같으면 두 변수에 1을 더합니다.

b) 값이 K와 일치하지 않거나 지금까지 경로에서 발견된 M의 연속 발생 횟수를 초과하는 경우 변수를 0으로 재설정합니다.

5단계: 트리를 탐색하는 동안 왼쪽과 오른쪽 모두에서 하위 노드의 값이 0인 경우 두 가지 방법으로 처리할 수 있습니다.

a) 변수가 M을 초과하지 않는지 확인하세요.

b) 그렇다면 조건을 만족하는 총 경로 수를 1만큼 늘립니다.

예

으아악

출력

으아악

결론

이 기사에서는 상단(즉, 리프)에서 끝 또는 루트까지의 경로 수를 계산하는 문제를 탐구합니다. 이러한 문제는 C++의 트리 순회 알고리즘과 재귀 기술을 사용하여 효율적으로 해결할 수 있습니다. 이진 트리를 순회하는 과정은 어려워 보일 수 있지만 예제를 사용하면 쉬워집니다.

위 내용은 최대 M개의 연속 노드와 값 K를 갖는 루트에서 리프까지의 경로 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!