greentea31's Note

https://leetcode.com/problems/longest-univalue-path/

풀이 과정

트리에서 같은 숫자로 이루어져 있는 가장 긴 경로를 구하는 문제이다.

DFS로 리프 노드에서부터 체크하면서 부모 노드의 값이 왼쪽 자식 노드의 값과 같으면 left 변수를 증가, 오른쪽 자식 노드의 값과 같으면 right 변수를 증가시키면서 정답을 구해주면 된다.

소스 코드

# 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 = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            
            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