LeetCode 687. Longest Univalue Path

파이썬 알고리즘 인터뷰 문제 44번(리트코드 687번) Longest Univalue Path
https://leetcode.com/problems/longest-univalue-path/

나의 풀이

# 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:
    path = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def helper(root):
            if not root:
                return -1
            left = -1
            right = -1
            if root.left:
                tempL = helper(root.left)
                if root.left.val == root.val:
                    left = tempL
                    self.path = max(self.path, tempL + 1)
            if root.right:
                tempR = helper(root.right)
                if root.right.val == root.val:
                    right = tempR
                    self.path = max(self.path, tempR + 1)
            if root.left and root.right and root.left.val == root.right.val == root.val:
                self.path = max(self.path, tempL + tempR + 2)
            depth = 1 + max(left, right)
            return depth
        helper(root)
        return self.path

다른 풀이1

# 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:
    path = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def helper(node):
            if not node:
                return 0
            left = helper(node.left)
            right = helper(node.right)

            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.path = max(self.path, left + right)
            return max(left, right)
            
        helper(root)
        return self.path

다른 풀이2

# 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:
        if not root: return 0
        res = 0
        def dfs(root):
            nonlocal res
            if not root: return 0
            if not root.left and not root.right: return 0
            left_len = dfs(root.left)
            right_len = dfs(root.right)
            if root.left and root.right and root.right.val == root.left.val == root.val:
                res = max(res, left_len + right_len + 2)
                return max(left_len, right_len) + 1
            if root.right and root.right.val == root.val:
                right_len += 1
                res = max(res, right_len)
                return right_len
            if root.left and root.left.val == root.val:
                left_len += 1
                res = max(res, left_len) 
                return left_len
            return 0

        dfs(root)
        return res