경로를 만족하지 않고 k보다 크거나 같은 노드를 제거하는 C++ 프로그램

이 문제에는 루트 노드에서 리프 노드까지의 경로가 완전히 정의된 이진 트리가 있습니다. 루트 노드부터 리프 노드까지의 모든 노드의 합은 상수 값 k보다 크거나 같아야 합니다. 따라서 합이 k보다 작은 경로의 모든 노드를 제거해야 트리의 나머지 경로가 k보다 커집니다. 여기서 기억해야 할 중요한 점은 노드가 여러 경로의 일부일 수 있으므로 해당 노드로 이어지는 모든 경로의 합이

루트 노드부터 리프 노드까지 합을 계산할 수 있습니다. 노드에 대한 재귀 호출이 완료되고 제어가 반환되면 왼쪽 및 오른쪽 경로의 합이

150K와 이런 나무가 있다고 가정해보세요 -

으아악

루트->왼쪽->왼쪽 경로의 합이 10 + 20 + 5(25, 150 미만)인 것을 보면 이를 잘라내고 5를 제거해야 합니다. 그다음에는 10->30->40으로 평가해보겠습니다. 150개 미만이므로 40개가 삭제됩니다.

이제 또 다른 경로인 10->20->35->50이 보입니다. 115의 합은 150보다 작으므로 50을 삭제합니다. 이제 남은 길은

으아악

모든 경로의 합이 150보다 크므로 더 이상 정리할 필요가 없습니다.

예

다음은 경로에 없고 그 합이 상수 값 k보다 크거나 같은 노드를 제거하는 방법을 보여주는 C++ 프로그램입니다. -

으아악

출력

으아악

완전히 가지치기된 우리의 나무 -

으아악

결론

보다시피 초기 관찰 후 DFS를 적용하고 각 호출에서 재귀 함수가 반환될 때 해당 노드의 합계를 계산하여 노드를 제거할 수 있습니다. 전반적으로 이것은 관찰과 방법론의 단순한 문제입니다.

위 내용은 경로를 만족하지 않고 k보다 크거나 같은 노드를 제거하는 C++ 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!