본문 바로가기
코딩문제

[LeetCode] 1026. Maximum Difference Between Node and Ancestor (Python)

by 컴돌이_예준 2022. 12. 9.

1026번 문제링크

https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/

 

Maximum Difference Between Node and Ancestor - LeetCode

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.com

문제설명

입력: TreeNode

출력: 정수값

트리의 같은 path에서 값이 가장 큰 것과 작은 것의 차이를 구하는 문제

*같은 path란 - 같은 조상을 가지며 같은 child를 가지는 관계

같은 색끼리 같은 path라고 보면 된다.

문제예제

[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 접근법이라고 하는데,, 참 대단하다.

출처: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/solutions/1657816/c-python-simple-solution-w-explanation-bottom-up-top-down-optimized-dfs-approaches/?orderBy=most_votes