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


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxAncestorDiff_wrong(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0

        def dfs(node):
            if not node.left and not node.right:
                return 0, 0
            l_diff, r_diff = 0, 0
            if node.left:
                t2 = node.val - node.left.val
                diff_l, diff_r = dfs(node.left)
                if t2 >= 0:
                    l_diff = max(t2, diff_l + t2, diff_r + t2)
                else:
                    l_diff = min(t2, diff_l + t2, diff_r + t2)
                self.res = max(self.res, abs(diff_l), abs(diff_r), abs(l_diff))

            if node.right:
                t2 = node.val - node.right.val
                diff_l, diff_r = dfs(node.right)
                if t2 >= 0:
                    r_diff = max(t2, diff_l + t2, diff_r + t2)
                else:
                    r_diff = min(t2, diff_l + t2, diff_r + t2)
                self.res = max(self.res, abs(diff_l), abs(diff_r), abs(r_diff))
            return l_diff, r_diff

        dfs(root)
        return self.res

    def maxAncestorDiff(self, root, mx=0, mn=100000):
        """
        :type root: TreeNode
        :rtype: int
        """
        return max(root.val - mn, mx - root.val,
                   self.maxAncestorDiff(root.left, max(root.val, mx), min(root.val, mn)),
                   self.maxAncestorDiff(root.right, max(root.val, mx), min(root.val, mn))) if root else 0
