1026번 문제링크
https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/
문제설명
입력: TreeNode
출력: 정수값
트리의 같은 path에서 값이 가장 큰 것과 작은 것의 차이를 구하는 문제
*같은 path란 - 같은 조상을 가지며 같은 child를 가지는 관계
문제예제
[8, 3, 1]
[8, 3, 6, 4]
[8, 3, 6, 7]
[8, 10, 14, 13]
에서 가장 차이가 큰 것은 | 8-1 | = 7 이므로 답은 7이다.
문제풀이
1. 각 path를 구한다.
2. path마다 가장 큰값과 가장 작은 값을 찾는다.
3. 가장 큰 값과 가장 작은 값의 차이가 가장 큰 값을 최대값으로 설정한다.
4. 최대값을 return
정답코드
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
self.MAX = 0
def find(node, path):
if not node:
return
path.append(node.val)
if node.left is None and node.right is None:
print(path)
self.MAX = max(max(path) - min(path), self.MAX)
find(node.left, path)
find(node.right, path)
path.pop()
find(root,[])
return self.MAX
풀이 후 생각정리
생각보다 복잡하게 코드를 짠 것 같기도 하다.
뭔가 더 단순하고 깔끔하게 코드를 짜고 싶은 욕심이 있는데, 생각만큼 쉽지 않은 것 같다.
그래서 다른 사람들은 어떻게 코드를 짰는지 보게 되었다.
PreOrder DFS - Top-Down 접근법이라고 하는데,, 참 대단하다.
'코딩문제' 카테고리의 다른 글
[백준 1753번] 최단경로 (Python 풀이) (0) | 2023.05.04 |
---|---|
[백준 15663번] N과 M (9) {Python 풀이} (0) | 2023.05.02 |
[LeetCode] 623. Add One Row to Tree (Python) (0) | 2022.10.05 |
[LeetCode] 1578. Minimum Time to Make Rope Colorful (Python) (1) | 2022.10.04 |
[LeetCode] 658. Find K Closest Elements (Python) (2) | 2022.09.29 |