엔지니어 게시판
LeetCode 솔루션 분류

[12/9] 1026. Maximum Difference Between Node and Ancestor

컨텐츠 정보

본문

1026. Maximum Difference Between Node and Ancestor 

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

 

Example 1:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Example 2:

Input: root = [1,null,2,null,0,3]
Output: 3

 

Constraints:

  • The number of nodes in the tree is in the range [2, 5000].
  • 0 <= Node.val <= 105
Accepted
187.7K
Submissions
247.9K
<div class="text-label-2 dark:text-dark-label-2 text-xs" style="border: 0px solid; box-sizing: border-box; --tw-border-spacing-x:0; --tw-border-spacing-y:0; --tw-translate-x:0; --tw-translate-y:0; --tw-rotate:0; --tw-skew-x:0; --tw-skew-y:0; --tw-scale-x:1; --tw-scale-y:1; --tw-pan-x: ; --tw-pan-y: ; --tw-pinch-zoom: ; --tw-scroll-snap-strictness:proximity; --tw-ordinal: ; --tw-slashed-zero: ; --tw-numeric-figure: ; --tw-numeric-spacing: ; --tw-numeric-fraction: ; --tw-ring-inset: ; --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,130,246,0.5); --tw-ring-offset-shadow:0 0 #0000; --tw-ring-shadow:0 0 #0000; --tw-shadow:0 0 #0000; --tw-shadow-colored:0 0 #0000; --tw-blur: ; --tw-brightness: ; --tw-contrast: ; --tw-grayscale: ; --tw-hue-rotate: ; --tw-invert: ; --tw-saturate: ; --tw-sepia: ; --tw-drop-shadow: ; --tw-backdrop-blur: ; --tw-backdrop-brightness: ; --tw-backdrop-contrast: ; --tw-backdrop-grayscale: ; -

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
# 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], maxval = float('-inf'), minval=float('inf')) -> int:
        if not root: return 0

        maxval = max(maxval, root.val)
        minval = min(minval, root.val)

        l = self.maxAncestorDiff(root.left, maxval, minval)
        r = self.maxAncestorDiff(root.right, maxval, minval)

        return max(l,r, abs(maxval-root.val), abs(minval-root.val))
전체 396 / 2 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0