最長同一値のパス

李金树の直径(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)