[LeetCode] 687. Longest Univalue Path
4311 ワード
🔦 質問リンク
🔊題 バイナリツリーのルートディレクトリが指定されている場合、パス内の各ノードは同じ値を持つ最長パスの長さを返します.このパスはルートディレクトリを通過するか通過しないかを指定します.2つのノード間のパス長は、ノード間のエッジ数で表されます.
▼▼▼▼草
この問題を解決するには、現在のノードのサブノードの値と、サブノードの値が最大何個連続しているかを理解する必要があります.
そのため、
まず、サブアイテムから最大数個の同じ値を戻り値として連続的に受信します.
第2に、サブノードの値はrootです.next.valで取得します.(ただし、root.nextがnoneでない場合)
🛠 コード#コード#
クラス変数の結果を使用して、値の再割り当てを回避します.
result変数に最値の更新を続行させます.
🎈 リファレンス
ブックリンク
🔊
파이썬 알고리즘 인터뷰冊の本を参考にしました.▼▼▼▼草
この問題を解決するには、現在のノードのサブノードの値と、サブノードの値が最大何個連続しているかを理解する必要があります.
そのため、
まず、サブアイテムから最大数個の同じ値を戻り値として連続的に受信します.
第2に、サブノードの値はrootです.next.valで取得します.(ただし、root.nextがnoneでない場合)
🛠 コード#コード#
class Solution:
result = 0
def longestUnivaluePath(self, root: TreeNode) -> int:
def dfs(root):
if not root:
return None
left = dfs(root.left)
right = dfs(root.right)
if root.left and root.val == root.left.val:
left += 1
else:
left = 0
if root.right and root.val == root.right.val:
right += 1
else:
right = 0
self.result = max(self.result, left + right)
return max(left, right)
dfs(root)
return self.resultクラス変数の結果を使用して、値の再割り当てを回避します.
result変数に最値の更新を続行させます.
🎈 リファレンス
ブックリンク
Reference
この問題について([LeetCode] 687. Longest Univalue Path), 我々は、より多くの情報をここで見つけました https://velog.io/@pyh8618/LeetCode-687.-Longest-Univalue-Pathテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol