각 노드가 자식 노드의 결과인 전체 이진 트리의 수

완전 이진 트리는 모든 상위 노드에 두 개의 하위 노드가 있거나 하위 노드가 없는 특별한 유형의 이진 트리입니다. 데이터 구조에서 이러한 유형의 트리는 균형 있고 조직화된 표현으로 간주됩니다. 완전한 이진 트리는 각 부모 노드가 자식 노드의 산물이라는 고유한 특성을 가질 수 있습니다.

이 기사에서는 C++를 사용하여 각 노드가 해당 자식 노드의 산물이 되도록 완전한 이진 트리 수를 계산하는 다양한 방법에 대해 설명합니다.

입력 및 출력 시나리오

예를 들어, {1, 5, 3, 4} 배열에는 1(1 x 1), 5(1 x 5), 3(1 x 3) 및 4(1 x 4)의 4개의 단일 노드만 있습니다.

주어진 배열에서 최대값보다 작은 각 요소의 모든 배수를 사용하여 배열에 배수가 있는 경우 완전한 이진 트리를 만들 수 있습니다. 따라서 배열에서 최대값을 찾습니다.

우리는 배열에서 더 작은 값이 더 큰 값의 배수가 될 수 있다는 것을 알고 있기 때문에 최소값에서 최대값까지 반복하여 이러한 이진 트리를 찾는 것부터 시작합니다.

동적 프로그래밍 사용

여기에서는 동적 프로그래밍을 사용하여 각 노드가 해당 하위 노드의 산물이 되도록 전체 이진 트리의 수를 찾습니다. 배열 요소를 반복하고 위 조건을 만족하는 가능한 트리를 찾습니다. 우리는 이러한 솔루션을 dp 벡터에 저장합니다.

• 먼저 C++의 INT_MAX 및 INT_MIN 상수를 사용하여 배열의 최대값과 최소값을 찾습니다. for 루프를 반복하여 최대값과 최소값을 업데이트합니다.

• 다음으로 배열의 최소값에서 최대값까지 반복하는 중첩 루프가 있습니다. 이 루프에서는 dp 벡터가 0이 아닌지 확인합니다.

• dp 벡터가 0이 아닌 경우 (j + j)부터 최대값까지 j의 배수에 대해 또 다른 for 루프를 실행합니다. 각 배수에 대해 둘 이상이 있는지 확인합니다.

• 2개 이상이면 가능한 전체 이진 트리 수는 arr[j] 및 arr[j]/k의 전체 이진 트리 수와 같습니다.

• 데이터 오버플로를 방지하기 위해 현재 업데이트된 dp 값 모듈로 1000000007을 결과에 추가합니다.

예

출력

Note- 여기서 이 프로그램의 시간 복잡도는 O(N^2)입니다.

결론

우리는 각 노드가 자신의 자식 노드의 산물이 되도록 전체 이진 트리의 수를 찾는 방법을 논의했습니다. 우리는 dp 벡터에 하위 문제에 대한 솔루션을 저장하여 동적 접근 방식을 사용하여 이 문제를 해결합니다. 간단한 중첩 for 루프를 사용하여 배열의 최소값에서 최대값까지 반복하고 원하는 속성을 가진 완전한 이진 트리의 가능한 수를 확인할 수 있습니다.

위 내용은 각 노드가 자식 노드의 결과인 전체 이진 트리의 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!