Leetcode - 687. Longest Univalue Path

문제

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

풀이

class Solution:
    def longestUnivaluePath(self, root: TreeNode):
        def get_path(node: TreeNode) -> int:
            left_path = right_path = 0

            if node.left:
                ll_path, lr_path = get_path(node.left)
                if node.left.val == node.val:
                    left_path = max(ll_path, lr_path) + 1
            if node.right:
                rl_path, rr_path = get_path(node.right)
                if node.right.val == node.val:
                    right_path = max(rl_path, rr_path) + 1
            res.append(left_path + right_path)
            return left_path, right_path

        res = [0]
        if root:
            get_path(root)
        return max(res)

DFS 재귀로 풀었다. 트리 문제는 무조건 그림을 손으로 그려보고, Path와 Node value가 어떻게 변하는지를 따져보면 쉽게 풀리는 것 같다.