java - 다중 트리 평가, 프로그램 마스터 및 알고리즘 마스터는 살펴봐야 합니다.

Question

필기시험 문제를 접했는데 전혀 도움을 요청할 수 없었습니다. . . . 알려진 클래스 정의는 다음과 같습니다. {code...} 입력 노드는 다음 조건을 충족합니다. 1. 노드의 값은 0보다 큰 부동 소수점 숫자입니다. 2. 노드의 하위 노드(및 하위 노드)의 값 )는 null이거나 0보다 큰 부동 소수점 숫자일 수 있습니다. 다음과 같은 프로그램 함수...

淡淡烟草味 · Answer

구체적인 코드를 작성하진 않았지만 아이디어를 이야기해보자
먼저 문제를 2단계로 나눈다
1단계, 리프가 아닌 노드의 값 결정
2단계, 리프 노드의 값 결정
처리 1단계 먼저 Step1이 처리된 후 Step2는 더 이상 필요하지 않습니다. 말씀드린 대로 부모 노드의 값에 따라 균등하게 나누면 됩니다.
1단계,
1-1단계: 리프가 아닌 각 노드를 아래에서 위로 순회하고 하위 노드를 합산하여 최소값을 결정합니다. 예를 들어, 가장 오른쪽 하위 트리의 최소값은 5.5입니다.
1-2단계: 위에서 아래로 리프가 아닌 노드를 레이어별로 결정합니다. 이는 측면 설명입니다. 첫 번째 레이어는 [100], 두 번째 레이어는 [10, 20, ?, ?]로 지정합니다. 에. 1-1 단계의 결과에 따르면, 두 번째 레이어의 최소값은 [10, 20, >60, >5.5] 이며, 100에서 최소값의 합을 뺀 후 균등하게 나눕니다. 결과는 [10, 20, 62.25, 7.75]
1-3단계: 위와 동일하고 세 번째 레이어를 결정합니다. 결과는 [5.5, 4.5] [9.5, 5.25, 5.25] [60, 1.125, 1.125] [6.625, 1.125]
여기서 마지막 그룹은 더 특별하고 고려해야 합니다. 7.75가 할당될 때 이미 왼쪽 하단에 5.5가 있으므로 7.75의 임의 숫자는 7.75-5.5=2.25입니다. 2.25를 양쪽에 균등하게 나눕니다. , 결과는 [6.625, 1.125]
1-4단계: 마지막 레이어는 장황하게 말할 필요가 없다고 믿습니다. 실제로는 2단계이므로 균등하게 나누면 됩니다.

伊谢尔伦 · Answer

방금 이 질문을 읽고 매우 흥미로웠습니다. 그러다가 생각이 나서 다음과 같은 질문을 했습니다.
제 생각은 재귀입니다.

계층적으로 탐색하여 각 레벨에서 결정된 값을 더하고, 빈 노드를 결정된 값의 합을 뺀 상위 노드의 값으로 나눕니다(질문의 요구 사항). 그런 다음 해당 노드가 리프 노드가 아닌 경우 위 방법에 따라 재귀합니다.
그러나 특정 리프 노드와 같은 각 노드의 값을 결정할 때는 무작위로 값을 할당해야 합니다. 해당 값 중 일부는 상위 노드에 의해 제한되고 일부는 상위 노드에 의해 제한되지 않습니다. , 예를 들어 두 번째 레이어의 세 번째 노드와 같이 의 두 리프 노드에 할당한 값으로 인해 해당 부모 노드가 요구 사항을 충족하지 못하는 경우 이는 질문의 의미를 충족하지 않습니다. 그래서 제가 원하는 것은 값이 결정될 때마다 이러한 노드의 값 범위를 전달하는 것입니다. 이러한 범위를 결정하면 몇 가지 문제가 발생하고 문제가 복잡해집니다.
범위가 결정됩니다. 각 빈 노드의 최대값은 상위 노드 값의 합에서 동일한 하위 노드의 값을 뺀 값이어야 합니다. 최소값은 해당 하위 노드의 가치 있는 요소의 합보다 커야 합니다. . 특정 범위만 결정되기 때문에 리프 노드의 일부 임의 값을 선택해도 나머지 노드가 질문의 의미를 충족하지 못하는 현상이 발생하지 않습니다. 일반적으로 동일한 부모 노드를 가진 각 빈 노드의 값은 상호 제약을 받습니다. 한 노드의 값이 자체적으로 만족하더라도 다른 노드는 요구 사항을 충족하지 못하게 됩니다. 예:

이런 방식으로 값을 취하면 로컬에서 만족하게 되어 다른 노드의 값이 요구 사항을 충족하지 못하게 됩니다. 따라서 아무런 제약 없이 예상치 못한 결과가 나올 수도 있습니다. 우리는 이러한 범위를 결정해야 합니다.

결론적으로 생각해본 내용이니 틀린 부분이 있을 수 있으니 정정 부탁드립니다.