44. Longest Univalue Path
6053 ワード
道しるべ と同じ値の最長パスが見つかりました.
ツリーの末端、リーフノードに移動し、値が一致する場合、次のように距離を段ごとに積み上げ、遡及的に解くことができます. <同じ値の移動距離の計算>
例の最初の入力値に対するツリーの距離と、ルートノードから右側のリーフノードまでの移動距離を示します.
ルートノードからDFSで再帰探索を行い,リフに到達するとその時点から逆トラッキングを行い,距離を蓄積する.
まず,DFS再帰探索を行う.
このようにして再びコールが返され、
ノードが存在しなくなった場合は、次のようにして値を返します.
存在しないノードに下がると、距離0が返されます.
この値は徐々に遡及するにつれて増加します.
この問題は同一値であるか否かを判別して距離を算出する問題であるため,サブノードが同一値であるか否かを決定する必要がある.
左側と右側のサブノードを別々にチェックし、現在のノード、すなわち親ノードと同じ場合、各ノードの距離を1ずつ増やします.
左サブノードと右サブノードの間の距離の和を結果とします. と最大値を最終結果とします.
次回のトレースバックでは、計算のために前の問題と同様のステータス値を設定し、親ノードに昇格させます. 親ノードに対してこれまでの距離を返します.
これまでプロトコルの最低価格が算出されていたため、ステータス値も
ただし、現在のノードは2つのサブノードを同時に接続できますが、現在のノードの親ノードは現在の2つのサブノードを同時に接続できません.
一方的なので、2つのサブノードのいずれかのサブノードしか選択できないのもツリーの特徴です. に従って、そのうちの1つの大きな値をステータス値に返信する.
1.状態値距離DFSの算出
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
result: int = 0
def longestUnivaluePath(self, root: TreeNode) -> int:
def dfs(node: TreeNode):
if node is None:
return 0
#존재하지 않는 노드까지 DFS 재귀 탐색
left = dfs(node.left)
right = dfs(node.right)
#현재 노드가 자식 노드와 동일한 경우 거리 1 증가
if node.left and node.left.val == node.val:
left += 1
else:
left = 0
if node.right and node.right.val == node.val:
right += 1
else:
right = 0
#왼쪽과 오른쪽 자식 노드 간 거리의 합 최댓값이 결과
self.result = max(self.result, left+right)
#자식 노드 상태값 중 큰 값 리턴
return max(left, right)
dfs(root)
return self.result
DFSにより例の最初の入力値に対するツリーの距離と、ルートノードから右側のリーフノードまでの移動距離を示します.
ルートノードからDFSで再帰探索を行い,リフに到達するとその時点から逆トラッキングを行い,距離を蓄積する.
まず,DFS再帰探索を行う.
このようにして再びコールが返され、
left, right
はそれぞれリーフノードに到着し、戻り値が得られる.ノードが存在しなくなった場合は、次のようにして値を返します.
if node is None: return 0
存在しないノードに下がると、距離0が返されます.
この値は徐々に遡及するにつれて増加します.
この問題は同一値であるか否かを判別して距離を算出する問題であるため,サブノードが同一値であるか否かを決定する必要がある.
左側と右側のサブノードを別々にチェックし、現在のノード、すなわち親ノードと同じ場合、各ノードの距離を1ずつ増やします.
左サブノードと右サブノードの間の距離の和を結果とします.
次回のトレースバックでは、計算のために前の問題と同様のステータス値を設定し、親ノードに昇格させます.
return max(left, right)
これまでプロトコルの最低価格が算出されていたため、ステータス値も
left + right
であるべきである.ただし、現在のノードは2つのサブノードを同時に接続できますが、現在のノードの親ノードは現在の2つのサブノードを同時に接続できません.
一方的なので、2つのサブノードのいずれかのサブノードしか選択できないのもツリーの特徴です.
Reference
この問題について(44. Longest Univalue Path), 我々は、より多くの情報をここで見つけました https://velog.io/@corone_hi/44.-Longest-Univalue-Pathテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol