리트코드 687번 Longest Univalue Path (python)

Problem

https://leetcode.com/problems/longest-univalue-path/description/

Solution

# Definition for a binary tree node.
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    result = 0
    
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode]):
            if node is None:
                return 0 
            
            left = dfs(node.left)
            right = dfs(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.result = max(self.result, left + right)
            return max(left, right)
        
        dfs(root)
        return self.result

dfs로 leaf까지 탐색해 내려가고 올라오면서 백트래킹하는 형태로 풀이할 수 있다.

리트코드 543번과 유사하게 풀되 노드의 val이 같은지 확인하는 과정만 추가하면 된다.

Reference

파이선 알고리즘 인터뷰 44번