[트리] 가장 긴 동일 값의 경로

687 | Longest Univalue Path
https://leetcode.com/problems/longest-univalue-path/

 

 

 

 

 

작성 코드

 

접근 방법

1. 현재 있는 노드의 val 과 왼쪽, 오른쪽의 val 이 같다면 dfs 탐색

 

# 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:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node, length):
            if node.left:
                if node.val != node.left.val:
                    return length
                else:
                    dfs(node.left, length + 1)
            if node.right:
                if node.val != node.right.val:
                    return length
                else:
                    dfs(node.right, length + 1)
        answer = dfs(root, 0)
        return answer

 

• 좌, 우를 더하는 코드가 없음
• 상단에서 같지 않으면 return 해버림, 1번 예시같은 경우 바로 return...

 

 

이상 코드

 

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    result: int = 0

    def longestUnivaluePath(self, root: TreeNode) -> int:
        def dfs(node: TreeNode):
            if node is None:
                return 0

            # 존재하지 않는 노드까지 DFS 재귀 탐색
            left = dfs(node.left)
            right = dfs(node.right)

            # 현재 노드가 자식 노드와 동일한 경우 거리 1 증가
            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

 

• 책에 있는 코드인데 Output Limit Exceeded 발생

 

 

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution(object):
    def longestUnivaluePath(self, root):
        longest = [0]
        def traverse(node):
            if not node:
                return 0
            left_len, right_len = traverse(node.left), traverse(node.right)
            left = (left_len + 1) if node.left and node.left.val == node.val else 0
            right = (right_len + 1) if node.right and node.right.val == node.val else 0
            longest[0] = max(longest[0], left + right)
            return max(left, right)
        traverse(root)
        return longest[0]

 

 

• 비슷한 코드지만 통과