[LeetCode] 687. Longest Univalue Path

https://leetcode.com/problems/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.

Example 1:

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 5).

Example 2:

Input: root = [1,4,5,4,4,null,5]
Output: 2
Explanation: The shown image shows that the longest path of the same value (i.e. 4).

---

시도했던 방법

리프노드로 내려가면서 변수에 저장

• DFS 방식으로 트리 전체를 순회하되, 매 노드마다 edges 라는 변수를 주어 부모노드와 자식노드의 값이 같다면 다음 노드로 넘어갈 때 1을 추가하는 방식으로 접근했다.
  

• 이 방식의 문제는 자식노드에서 리턴된 값이 실제 연결된 리스트의 길이를 가리키지 못한다는 점이었다. 기존에 부모노드에서 내려오던 edges가 새로운 value를 만나 0으로 초기화 되었을 때, 다시 리턴시켜야 하는 값이 부모노드에서 이어져오던 edges인지, 자식노드에서 초기화 된 edges인지 구별을 못하기 때문에 원하는 값이 나오지 못하는 것을 확인했다.

리프노드까지 도달한 후 올라오면서 변수에 저장

• 문제를 해결하기 위해 반대로 리프노드에서 올라오면서 값을 넘겨주는 방식을 사용하기로 했다. 이렇게 접근하면 자식노드에서부터 올라오는 최신화된 값이 부모노드로 전달되어 루트까지 오기 때문에 제대로 값을 구할 수 있다.

• 왼쪽 자식노드에서 올라온 값과, 오른쪽 자식노드에서 올라온 값을 가지고 부모 노드의 밸류값과 비교하여 조건에 맞는 edges값을 부모노드로 보내는 방식으로 접근하였다.

• 다만, 이 방식으로 접근하면 한 줄로 이어진 가장 긴 경로를 반환하는 것이 아닌, 밸류가 같은 노드사이의 연결된 간선의 갯수를 리턴하게 된다.

자식 노드에서 올라온 값을 처리하는 방법

• 따라서 자식노드에서 올라온 값을 현재 노드의 밸류와 비교하여 경로가 이어졌는지 끊어졌는지 확인한 후, 양쪽 자식 노드의 길이 합을 최대 길이와 비교하여 최신화한 후, 부모 노드로 넘겨주는 값은 둘 중 긴 경로의 값만 넘겨주는 식으로 수정하였다.

코드

# 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:
        self.max_len = 0

        def dfs(node, prev):
            if node is None: return 0

            left_edges = dfs(node.left, node.val)
            right_edges = dfs(node.right, node.val)
            
            self.max_len = max(self.max_len, left_edges + right_edges)
            return max(left_edges, right_edges) + 1 if node.val == prev else 0

        dfs(root, 0)
        return self.max_len

---

참고

543. Diameter of Binary Tree

• 이 문제도 위와 같은 방식으로 풀리는 문제였는데, 위 문제는 노드마다 주어진 밸류값이 달라 매 탐색마다 값을 비교하여 경로가 연결되는지, 끊어지는지를 확인하였지만 이 문제는 노드의 값을 비교하지 않고 그저 가장 긴 경로만 반환하면 된다.

• 따라서 위 문제에서 모든 노드의 값이 똑같다는 식으로 가정을 하고 풀면 쉽게 풀 수 있다.

코드

# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.max_len = 0

        def dfs(node):
            if node is None: return 0
            
            left_len = dfs(node.left)
            right_len = dfs(node.right)

            self.max_len = max(self.max_len, left_len + right_len)
            return max(left_len, right_len) + 1
        
        dfs(root)
        return self.max_len