가장 긴 동일 값의 경로

이진 트리의 직경 ( leetcode 543 )과 아주 아주 !! 유사한 DFS 문제입니다.
코드를 보면서 같이 풀어보겠습니다 🔥🔥🔥

Leetcode 687. Longest Univalue Path

Given the root of a binary tree, return the length of the longest path, 
where each node in the path has the same value. 
This path may or may not pass through the root.

The length of the path between two nodes
is represented by the number of edges between them.

Input: root = [5,4,5,1,1,5]
Output: 2

동일한 값을 지닌 가장 긴 경로를 찾는 문제입니다.
얼핏봐도 BFS 로는 절대 풀 수 없다는걸 느낄 수 있습니다. 바로 전에 풀었던 543번과 마찬가지로 리프 노드까지 DFS 로 내려간 다음, 값이 일치할 경우 거리를 차곡차곡 쌓아서 올려가며 백트래킹하는 형태로 풀 수 있습니다.

정답코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# 리트코드안에서는 내부의 툴로 자동으로 동작?? 합니다 !! 

# class Solution:
#     def longestUnivaluePath(self, root: TreeNode) -> int:


root = TreeNode(5)
left = TreeNode(4)
right = TreeNode(5)
root.right = right
root.left = left

left1 = TreeNode(1)
right1 = TreeNode(1)
left.left = left1
left.right = right1

left2 = TreeNode(None)
right2 = TreeNode(5)
right.left = left2
right.right = right2

# 제출 할 때는 다 빼고 제출 해야 합니다 !!!!

result = 0

def dfs(node):
    global result
    if node is None:
        return 0
    # 없는거까지 내려가면 ( 리프노드의 자식, None 값 ) -> 리턴 0 (거리가 0 )

    left = dfs(node.left)
    right = dfs(node.right)
    # 제일 말단(리프)까지 재귀로 타고 들어감 
    # => 리프노드의 자식노드에서는 리턴 0 이므로

    # 리프노드 도착했을때부터 시작 ( 백트래킹, 거리를 차곡차곡 쌓아나감 )
    if node.left and node.left.val == node.val:
        # node 의 왼쪽 자식 노드가 존재하고, 그 자식 노드의 값과 현대 노드의 값이 같을 때
        left += 1
    else :
        left = 0

    if node.right and node.right.val == node.val:
        # node 의 오른쪽 자식 노드가 존재하고, 그 자식 노드의 값과 현대 노드의 값이 같을 때
        right += 1
    else :
        right = 0

    #왼쪽과 오른쪽 자식 노드 간 거리의 합 최댓값이 결과
    result = max(result, left + right)

    #자식 노드 상태값 중 큰 값 리턴
    return max(left, right)

dfs(root)
print(result)