leetcode124.두 갈래 나무의 최대 경로와
1. 제목 설명
비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다.
본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다.
예 1:
입력: [1,2,3]
1 /\ 2 3
출력: 6 예 2:
입력: [-10,9,20,null,null,15,7]
-10 /\ 9 20 / \ 15 7
출력: 42
2. 문제풀이 사고방식
나무의 각 점에 대해 차례차례 좌우 나무를 계산한 후에 우리는 좌우 나무를 유지하는 두 개의 최대 경로를 이 점과 연결하면 이 점을 할점으로 하는 최대 경로를 얻을 수 있다.
모든 결점에 대해 말하자면 왼쪽 아이의 결점을 지나는path의 합이 큰지 오른쪽 아이의 노드를 지나는path의 합이 큰지 알아야 한다. 귀속 함수 dfs는 비교적 큰path와 값을 이 노드의 반환값으로 저장한다.귀속 함수 반환값은 현재 결점을 루트 결점으로 하고 잎 노드에 대한 최대 경로의 합(왼쪽 경로 또는 오른쪽 경로)으로 정의할 수 있습니다.
귀속 함수에서 현재 결점이 존재하지 않으면 0을 되돌려줍니다.그렇지 않으면 각각 좌우 서브노드에 대해 귀속 함수를 호출한다. 경로와 마이너스가 될 수 있기 때문에 여기는 당연히 마이너스의 경로와 0을 더하는 것을 원하지 않기 때문에 0에 비해 비교적 큰 것을 취하면 더하지 않거나 더하면 정수를 넣어야 한다.그리고 전역 최대치 결과res를 업데이트합니다. 바로 왼쪽 결점을 종점으로 하는 최대 path의 합과 오른쪽 결점을 종점으로 하는 최대 path의 합, 그리고 현재 결점 값을 합치면 완전한 경로를 구성합니다.반면에 반환값은 left와right의 비교적 큰 값에 현재 결점 값을 추가합니다. 반환값의 정의는 현재 결점을 종점으로 하는 path의 합이기 때문에 left와right에서 비교적 큰 값만 얻을 수 있습니다. 두 가지 모두 원하지 않습니다.
참조 링크:https://www.cnblogs.com/grandyang/p/4280120.html
3. 코드 구현 # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import sys
class Solution(object):
def __init__(self):
self.ans=-sys.maxsize
def dfs(self,root):
if not root:
return 0
# ，
left=max(0,self.dfs(root.left))
right=max(0,self.dfs(root.right))
self.ans=max(self.ans,left+right+root.val)
return max(left,right)+root.val
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.dfs(root)
return self.ans
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」
해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다.
빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
나무의 각 점에 대해 차례차례 좌우 나무를 계산한 후에 우리는 좌우 나무를 유지하는 두 개의 최대 경로를 이 점과 연결하면 이 점을 할점으로 하는 최대 경로를 얻을 수 있다.
모든 결점에 대해 말하자면 왼쪽 아이의 결점을 지나는path의 합이 큰지 오른쪽 아이의 노드를 지나는path의 합이 큰지 알아야 한다. 귀속 함수 dfs는 비교적 큰path와 값을 이 노드의 반환값으로 저장한다.귀속 함수 반환값은 현재 결점을 루트 결점으로 하고 잎 노드에 대한 최대 경로의 합(왼쪽 경로 또는 오른쪽 경로)으로 정의할 수 있습니다.
귀속 함수에서 현재 결점이 존재하지 않으면 0을 되돌려줍니다.그렇지 않으면 각각 좌우 서브노드에 대해 귀속 함수를 호출한다. 경로와 마이너스가 될 수 있기 때문에 여기는 당연히 마이너스의 경로와 0을 더하는 것을 원하지 않기 때문에 0에 비해 비교적 큰 것을 취하면 더하지 않거나 더하면 정수를 넣어야 한다.그리고 전역 최대치 결과res를 업데이트합니다. 바로 왼쪽 결점을 종점으로 하는 최대 path의 합과 오른쪽 결점을 종점으로 하는 최대 path의 합, 그리고 현재 결점 값을 합치면 완전한 경로를 구성합니다.반면에 반환값은 left와right의 비교적 큰 값에 현재 결점 값을 추가합니다. 반환값의 정의는 현재 결점을 종점으로 하는 path의 합이기 때문에 left와right에서 비교적 큰 값만 얻을 수 있습니다. 두 가지 모두 원하지 않습니다.
참조 링크:https://www.cnblogs.com/grandyang/p/4280120.html
3. 코드 구현 # Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import sys
class Solution(object):
def __init__(self):
self.ans=-sys.maxsize
def dfs(self,root):
if not root:
return 0
# ，
left=max(0,self.dfs(root.left))
right=max(0,self.dfs(root.right))
self.ans=max(self.ans,left+right+root.val)
return max(left,right)+root.val
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.dfs(root)
return self.ans
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」
해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다.
빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import sys
class Solution(object):
def __init__(self):
self.ans=-sys.maxsize
def dfs(self,root):
if not root:
return 0
# ，
left=max(0,self.dfs(root.left))
right=max(0,self.dfs(root.right))
self.ans=max(self.ans,left+right+root.val)
return max(left,right)+root.val
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.dfs(root)
return self.ans
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
