44. Longest Univalue Path

🎯 leetcode - 687. Longest Univalue Path

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 44번 문제

📌 날짜

2020.02.15

📌 시도 횟수

5 try

💡 Code

class Solution:
    longest = 0

    def longestUnivaluePath(self, root: TreeNode) -> int:
        def dfs(node):
            if not node:
                return 0
			
            # 리프 노드까지 dfs 재귀 실행
            left = dfs(node.left)
            right = dfs(node.right)
			
            if node.left and node.left.val == node.val:
                left += 1
            else: # 값이 다르면 이전 상태값을 0으로 재설정함
                left = 0
            if node.right and node.right.val == node.val:
                right += 1
            else: # 값이 다르면 이전 상태값을 0으로 재설정함
                right = 0

            self.longest = max(self.longest, left + right)
            return max(left, right) # 상태값이 더 큰 값이 현재노드의 상태값

        dfs(root)
        return self.longest

💡 문제 해결 방법

• 예시 이진 트리
  
• DFS 탐색 순서와 그 역방향으로 상태값/최대 경로 길이(longest)가 갱신됨
  
  

- 이전 43번 문제와 마찬가지로,
리프노드까지 탐색한 다음 다시 루트까지 거슬러 올라가면서 차례대로 현재 노드의 상태값과,
최대 경로 길이 값을 갱신해준다.

- 단, 본 문제에서는 left, right를 구할 때 제한 조건이 있다.
왼쪽 노드와 값이 같다면 left + 1을, 오른쪽 노드와 값이 같다면 right + 1을 해준다.
하지만 만약 값이 다르다면, 해당 상태값은 이전 상태값과 상관 없이
바로 0으로 갱신된다. 따라서 값이 다르다면 left(또는 right) = 0

- 상태값 구하기: 위의 과정을 통해 left, right를 구한 후
left, right중 더 큰 값이 현재노드의 상태값이 된다.

- 최대 경로 길이도 위의 과정을 통해 left, right를 구한 후,
self.longest = max(self.longest, left + right)를 통해 최대 길이를 갱신한다.

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 현재 노드 node에 대하여...

✔ node.left(또는 node.right)의 값과 node의 값이 같은 경우
⭐ node.left(또는 node.right)의 상태값인 left(right)를 그대로 사용한다.

✔ 하지만 값이 다른 경우,
⭐ node.left(node.right)의 상태값인 left(right)를 그대로 사용하지 않고
0으로 갱신시킨후에, 그대로 상태값/최대경로길이 계산을 한다는 점

이 생각하기 어려웠다.

---