aboutsummaryrefslogtreecommitdiff
path: root/max_diff_node_ancestor.py
blob: e1a0648ec661ce0335e580560b216adc48f18dd6 (plain)
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