1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
# 1026. Maximum Difference Between Node and Ancestor
"""
given the 'root' of a binary tree, find the maximum value 'v' for which there
exists different nodes 'a' and 'b' where 'v = | a.val - b.val |' and 'a' is
an ancesotr of 'b'. a node 'a' is an ancesotr of 'b' if either any child if
'a' is equal to 'b' or any child 'a' is an ancestor of 'b'.
"""
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def helper(self, root, min_val, max_val):
if not root:
return
self.diff = max(
self.diff, max(abs(min_val - root.val), abs(max_val - root.val))
)
min_val = min(min_val, root.val)
max_val = max(max_val, root.val)
self.helper(root.left, min_val, max_val)
self.helper(root.right, min_val, max_val)
def maxAncestorDiff(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
self.diff = 0
self.helper(root, root.val, root.val)
return self.diff
if __name__ == "__main__":
obj = Solution()
print(
obj.maxAncestorDiff(root=[8, 3, 10, 1, 6, None, 14, None, None, 4, 7, 13])
) # expect: 7
print(obj.maxAncestorDiff(root=[1, None, 2, None, 0, 3])) # expect: 3
|