[LeetCode] 687. Longest Univalue Path

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

이진 트리의 루트가 주어지면 경로의 각 노드가 동일한 값을 갖는 가장 긴 경로의 길이를 반환합니다. 이 경로는 루트를 통과하거나 통과하지 않을 수 있습니다. 두 노드 사이의 경로 길이는 노드 사이의 가장자리 수로 표시됩니다.

✍️ 풀이

---

문제를 해결하기 위해선 현재노드에서 자식노드의 값과 자식에서 같은 값이 최대 연속 몇개 였는지에 대해 알아야 한다.

따라서,
첫번째로 자식에서 같은 값이 최대 연속 몇개 였는지 반환값으로 받아온다.
두번째로는 자식노의 값을 root.next.val을 통해서 얻어온다. (단, root.next가 none이 아닐 때)

🛠 코드

---

class Solution:
    result = 0
    def longestUnivaluePath(self, root: TreeNode) -> int:
        def dfs(root):
            if not root:
                return None

            left = dfs(root.left)
            right = dfs(root.right)

            if root.left and root.val == root.left.val:
                left += 1
            else:
                left = 0
            if root.right and root.val == root.right.val:
                right += 1
            else:
                right = 0

            self.result = max(self.result, left + right)
            return max(left, right)
        dfs(root)
        return self.result

---

📝 정리

---

클래스 변수 result를 사용해 값이 재할당 되지 않도록 했다.
result 변수에 계속해서 최댓값을 갱신하도록 한다.

🎈 참고

---

Book 링크