두 갈래 트리 문제 - 두 갈래 트리에서 지정한 값의 최대 경로 길이를 누적 찾습니다.
2733 단어 데이터 구조와 알고리즘
두 갈래 나무의 머리 노드 헤드와 32비트 정수sum를 정하고, 두 갈래 나무의 절점 값 유형은 정형이며, 누적과sum의 최장 경로 길이를 구한다.경로란 한 노드에서 아래로 내려가 매번 최대 한 아이의 노드를 선택하거나 구성된 노드 체인을 선택하지 않는 것을 말한다.
[기본적인 사고방식]
다음은python3.5로 이루어진 코드입니다.
def getMaxLength(root, K):
def getLengthByPreOrder(root, K, preSum, level, length, map):
if not root:
return length
curSum = preSum + int(root.val)
if curSum not in map:
map[curSum] = level
if curSum-K in map:
length = max(level - map.get(curSum-K), length)
length = getLengthByPreOrder(root.left, K, curSum, level+1, length, map)
length = getLengthByPreOrder(root.right, K, curSum, level+1, length, map)
if level == map.get(curSum):
map.pop(curSum)
return length
if not root:
return
map = {}
map[0] = 0
return getLengthByPreOrder(root, K, 0, 1, 0, map)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
