[2024] Day11. 1026. Maximum Difference Between Node and Ancestor

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 11일 (목)
Leetcode daily problem

1026. Maximum Difference Between Node and Ancestor

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

Problem

이진 트리의 루트가 주어질 때, 서로 다른 노드 a와 b가 존재하는 최대값 v를 찾습니다. v = |a.val - b.val|

Solution

Tree (binary tree)

주어진 이진 트리 노드를 순회하면서 가장 큰 값과 가장 작은 값을 찾아서, 해당 값의 차이가 가장 큰 것을 찾아나가면 된다.
dfs를 통해서 탐색해나간다!

Code

# 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:

        def dfs(node, min_val, max_val):
            if not node:
                return abs(max_val - min_val)
            
            min_val = min(min_val, node.val)
            max_val = max(max_val, node.val)
            
            left = dfs(node.left, min_val, max_val)
            right = dfs(node.right, min_val, max_val)
            
            return max(left, right)

        return dfs(root, float('inf'), float('-inf'))

Complexicity

시간 복잡도

트리의 모든 노드를 한 번 방문하므로 시간 복잡도는 O(N)이다.
(N : 노드의 총 수)

공간 복잡도

재귀 함수 dfs가 호출될 때마다 함수 호출 스택에 추가된다.
따라서 이 코드의 공간 복잡도는 재귀 호출의 최대 깊이에 따라 결정되는데
최악의 경우, 트리의 높이가 N이면, 재귀 호출의 깊이도 N이 된다.
따라서 공간 복잡도는 O(N)이다.

---