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

제약 조건

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000
The depth of the tree will not exceed 1000.

전체 코드

# 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 __init__(self):
        self.answer=0
        
    def dfs(self,current)->int:
        # when leaf node, then stop recursion
        if current==None or(current.left==None and current.right==None):
            return 0
        else:
            left_length=0
            right_length=0
            
            if current.left!=None:
                go_left=self.dfs(current.left)
                if current.val == current.left.val:
                    left_length=go_left+1
            
            if current.right!=None:
                go_right=self.dfs(current.right)
                if current.val == current.right.val:
                    right_length=go_right+1
            
            self.answer=max(self.answer, left_length+right_length)
            
            return left_length if left_length>right_length else right_length
            
                
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:

        self.dfs(root)
        return self.answer

효율성

Runtime: 449 ms, faster than 63.64% of Python3 online submissions for Longest Univalue Path.
Memory Usage: 18 MB, less than 51.82% of Python3 online submissions for Longest Univalue Path.

해설

생각해 봐야 하는 입력

[5,5,5,5,5,5] 의 입력이 주어졌다고 하자. 정답부터 말하면 4다.

처음에는 5인 줄 알았으나, Expected = 4 였다.
이유는 두 노드(값이 같음) 사이의 가장 긴 '경로'이기 때문이다.
예를 들면 다음과 같다.

풀이 흐름