[트리] 리트코드 687: longest-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