[ツリー]ツリーコード687:longth-univalue-path
# https://leetcode.com/problems/longest-univalue-path
# 내 풀이
# 리프부터 올라가면서, 부모랑 달라지면 처음부터 다시 쌓는다.
class Solution:
longest = 0
odd_val = 10000
def longestUnivaluePath(self, root: TreeNode) -> int:
# 실수: 문제 조건에서 root가 비어있을 수 있음을 간과
if not root:
return 0
def dfs(node: TreeNode, parent_val):
if not node:
return -1, self.odd_val
a= b = -1
a, a_val = dfs(node.left, node.val)
b, b_val = dfs(node.right, node.val)
# 자식들이 모두 값이 달라졌으면 현재노드의 상태값은 0이다 (처음부터 쌓기)
ret = 0
# 양쪽 자식 모두 부모(현재노드)와 값이 같다면
if (a_val == node.val and b_val == node.val):
self.longest = max(self.longest, a+b+2)
# 현재노드의 상태값 저장
ret = max(a, b) + 1
# 한쪽 자식만 현재노드와 값이 같다면
elif (a_val == node.val):
ret = a + 1
elif (b_val == node.val):
ret = b + 1
# 한쪽 자식 방향으로만 같은 값이 있는 경우
self.longest = max(self.longest, ret)
return ret, node.val
dfs(root, root.val)
return self.longest
Reference
この問題について([ツリー]ツリーコード687:longth-univalue-path), 我々は、より多くの情報をここで見つけました https://velog.io/@ember/트리-LTC-longest-univalue-pathテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol