Leetcode 687: 최장 동치 경로(초상세 해법!!!)

두 갈래 트리를 지정해서 가장 긴 경로를 찾으십시오. 이 경로의 모든 노드는 같은 값을 가지고 있습니다.이 경로는 통과할 수도 있고 루트 노드를 통과하지 않을 수도 있다.
참고: 두 노드 사이의 경로 길이는 둘 사이의 모서리로 표시됩니다.
예 1:
입력:

              5
             / \
            4   5
           / \   \
          1   1   5

출력:

2

예 2:
입력:

              1
             / \
            4   5
           / \   \
          4   4   5

출력:

2

주의: 주어진 두 갈래 나무는 10000개의 결점을 넘지 않습니다.나무의 높이는 1000을 넘지 않는다.
문제 풀이 사고방식
유사한 문제
Leetcode 124: 두 갈래 나무의 최대 경로와 (초상세 해법!!!)
Leetcode 543: 두 갈래 나무의 지름(초상세 해법!!!)
우리는 함수longestUnivalue를 정의하여 좌우 양쪽 중 가장 큰 경로의 길이를 되돌려줍니다. 이때 우리는 네 가지 상황을 고려합니다.

root.left == root == root.right

root.left == root

root.right == root

root.left ！= root != root.right

첫 번째 상황에 대해 이때쯤 아이와 뿌리가 같을 때 우리는 우리의 최대 길이res=max(res,l+r+2)를 갱신하고 max(l,r)+1로 돌아가야 한다.두 번째 상황에 대해 왼쪽 아이와 뿌리가 같으면 최대 길이res=max(res,l+1)를 업데이트하고 l+1로 돌아가야 한다.세 번째 상황에 대해 오른쪽 아이와 뿌리가 같으면 최대 길이res=max(res,r+1)를 갱신하고 r+1로 돌아가야 한다.네 번째 경우, 이때 0 로 돌아가기만 하면 된다.

class Solution:
    def longestUnivaluePath(self, root: 'TreeNode') -> 'int':
        res = 0
        def longestUnivalue(root):
            nonlocal res
            if not root:
                return 0
            l = longestUnivalue(root.left)
            r = longestUnivalue(root.right)
            if root.left and root.right and root.left.val == root.val == root.right.val:
                res = max(res, l + r + 2)
                return max(l, r) + 1
            elif root.left and root.left.val == root.val:
                res = max(res, l+1)
                return l + 1
            elif root.right and root.right.val == root.val:
                res = max(res, r+1)
                return r + 1
            else:
                return 0
            
        longestUnivalue(root)
        return res

위의 코드를 살짝 간략하게 할게요.

class Solution:
    def longestUnivaluePath(self, root: 'TreeNode') -> 'int':
        res = 0
        def longestUnivalue(root):
            nonlocal res
            if not root:
                return 0
            l = longestUnivalue(root.left)
            r = longestUnivalue(root.right)
            pl, pr = 0, 0
            if root.left and root.left.val == root.val:
                pl = l + 1
            if root.right and root.right.val == root.val:
                pr = r + 1
            res = max(res, pl + pr)
            return max(pl, pr)
            
        longestUnivalue(root)
        return res

이 질문의 다른 언어 버전을 GitHub Leetcode에 추가했습니다.
문제가 있으면 여러분이 지적해 주시기 바랍니다!!!