Longest Univalue Path - LeetCode

문제 접근 🤔

• 동일한 값을 가진 가장 긴 경로를 찾는 문제
• 리프 노드까지 DFS를 통해 탐색하여 내려간 후, 현재 노드와 왼쪽 노드 혹은 오른쪽 노드의 값이 일치할 경우 거리를 올려주며 백트래킹 한다.
• 경로의 값은 현재 노드와 왼쪽에서 동일 값을 가진 길이와 오른쪽에서 동일 값을 가진 길이을 합하면 된다.
• 이 값이 구하는 경로의 길이이므로 변수 longest 에 저장하되, 경로의 길이 보다 저장 값이 더 큰 경우가 있을 수 있으므로 longest = max(longest, leftCnt + rightCnt) 이다.
• 다만 함수가 return 되는 값은 이 값과 상관 없이 이 부분에서의 상태 값이므로 leftCnt 와 rightCnt 중 큰 값을 선택하면 된다. (경로의 길이는 편도이므로 왼쪽과 오른쪽 중 택 1을 해야한다.)
  
  
  

놓쳤던 부분 😅

• return max(leftCnt, rightCnt) 이 부분을 먼저 떠올리지 못해서 고민하다가 다른 사람의 풀이를 보고 해결하였다.
• 경로의 길이는 편도라는 점 ❗️
  
  
  

코드 😁

파이썬 코드(214 ms)

class Solution:
    def longestUnivaluePath(self, root):
        self.longest = 0
        def dfs(node):
            if not node: return 0

            leftCnt, rightCnt = dfs(node.left), dfs(node.right)
            if node.left and node.val == node.left.val:
                leftCnt += 1
            else:
                leftCnt = 0
            if node.right and node.val == node.right.val:
                rightCnt += 1
            else:
                rightCnt = 0
            self.longest = max(self.longest, leftCnt + rightCnt)
            return max(leftCnt, rightCnt)
            
        dfs(root)
        return self.longest

자바스크립트 코드(161 ms)

const longestUnivaluePath = (root) => {
    let longest = 0

    const dfs = (node) => {
        if(!node) {
            return 0;
        }
        let [leftCnt, rightCnt] = [dfs(node.left), dfs(node.right)]
        if(!!node.left && node.val === node.left.val) {
            leftCnt++
        } else {
            leftCnt = 0
        }
        if(!!node.right && node.val === node.right.val) {
            rightCnt++
        } else {
            rightCnt = 0
        }
        longest = Math.max(longest, leftCnt + rightCnt)
        return Math.max(leftCnt, rightCnt)
    }
    dfs(root)
    return longest
};