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.

 
Note:

The number of nodes in the tree is between 2 and 5000.
Each node will have value between 0 and 100000.

Difficulty: interview

Starter 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: TreeNode) -> int:
        

Solutions:
# 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: TreeNode) -> int:
        self.res = 0
        def helper(node, path_max, path_min):
            if not node:
                return 0
            path_max = max(path_max, node.val)
            path_min = min(path_min, node.val)
            self.res = max(self.res, path_max - path_min)
            helper(node.left, path_max, path_min)
            helper(node.right, path_max, path_min)
        if not root:
            return 0
        helper(root, root.val, root.val)
        return self.res

# 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:
    answer = 0
    def maxAncestorDiff(self, root: TreeNode) -> int:
        def dfs(node, max_v, min_v):
            # max값 (answer) 갱신
            self.answer = max(self.answer, abs(max_v - node.val))
            self.answer = max(self.answer, abs(min_v - node.val))
                
            if node.left:
                dfs(node.left, max(max_v, node.val), min(min_v, node.val))
            if node.right:
                dfs(node.right, max(max_v, node.val), min(min_v, node.val))
        
        dfs(root, root.val, root.val)
        return self.answer

# 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
# Think: For each subtree, find the minimum value and maximum value of its descendants.
class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.res = 0
        def helper(node, max_val, min_val):
            # think: we use the recursive way to traverse through the tree.
            if not node:
                self.res = max(self.res, max_val - min_val)
                return
            helper(node.left, max(max_val, node.val), min(min_val, node.val))
            helper(node.right, max(max_val, node.val), min(min_val, node.val))
        helper(root, 0, 100000)
        return self.res

# 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: TreeNode) -> int:
        
        
        self.max_diff = -float(\"inf\")
        
        
        def helper(root, ancestors):
            if root is None:
                return
            
            for ancestor in ancestors:
                if abs(root.val - ancestor) > self.max_diff:
                    self.max_diff = abs(root.val - ancestor)
            
            helper(root.left, ancestors + [root.val])
            helper(root.right, ancestors + [root.val])
        
        helper(root, [root.val])
        
        return self.max_diff

# 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: TreeNode) -> int:
        return self.maxAncestorDiffHelper(root, [], 0)
    
    def maxAncestorDiffHelper(self, root: TreeNode, ancestors, maxV: int) -> int:
        if root is None:
            return 0
        # if root.left is None and root.right is None:
        #     return 0
        for a in ancestors:
            maxV = max(maxV, abs(a-root.val))
        ancestors.append(root.val)
        maxV = max(
            maxV,
            self.maxAncestorDiffHelper(root.left, ancestors, maxV),
            self.maxAncestorDiffHelper(root.right, ancestors, maxV)
        )
        ancestors.pop()
        return maxV
            


# 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: TreeNode) -> int:
        return self.helper(root, [], 0)
    
    def helper(self, root, anc,prevmax):
        if root == None:
            return prevmax
        real_prev = prevmax
        for a in anc:
            prevmax = max(prevmax, abs(a-root.val))
        anc.append(root.val)
        real_anc = list(anc)
        left = self.helper(root.left, anc, prevmax)
        right = self.helper(root.right, real_anc, prevmax)
        return max(left,right)


def maxDiff(root, arr):
        a = 0
        for i in arr:
            a = max(a,abs(i-root.val))
        b = 0
        c = 0
        if (root.left):
            b = maxDiff(root.left, arr+[root.val])
        if (root.right):
            c = maxDiff(root.right, arr+[root.val])
        return max(a,b,c)
#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: TreeNode) -> int:
        return maxDiff(root,[])


# 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: TreeNode) -> int:
        def helper(root):
            if(root==None):
                return([])
            left = helper(root.left)
            right = helper(root.right)
            temp = []
            for i in range(len(left)):
                if(abs(left[i]-root.val) > self.ans):
                    self.ans = abs(left[i]-root.val)
                temp.append(left[i])
            for i in range(len(right)):
                if(abs(right[i]-root.val)> self.ans):
                    self.ans = abs(right[i]-root.val)
                temp.append(right[i])
            temp.append(root.val)
            return(temp)
        self.ans= 0
        helper(root)
        return(self.ans)

def findMaxDiff(node, collected):
    if not node:
        return float('-inf')
    cur_max = 0
    for v in collected:
        cur_max = max(cur_max, abs(v - node.val))
    left_max = findMaxDiff(node.left, collected + [node.val])
    right_max = findMaxDiff(node.right, collected + [node.val])
    return max(cur_max, left_max, right_max)

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        return findMaxDiff(root, [])


# 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: TreeNode) -> int:
        maxel = -float('inf')
        
        def traverse(root,anc,maxel):
            if root:
            
                for i in anc:
                    val = abs(i-root.val)
                    # print(val,maxel)
                    maxel = max(maxel,val)
                anc.append(root.val)
                maxel = traverse(root.right,anc,maxel)
                maxel = traverse(root.left,anc,maxel)
                anc.pop(-1)
            return maxel
        return traverse(root,[],maxel)
                


# 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(object):
    def maxAncestorDiff(self, root):
        \"\"\"
        :type root: TreeNode
        :rtype: int
        \"\"\"
        if not root: return 0
        return self.helper(root, root.val, root.val)
    
    def helper(self, node, high, low):
        if not node:
            return high - low
        high = max(high, node.val)
        low = min(low, node.val)
        return max(self.helper(node.left, high, low), self.helper(node.right,high,low))
        

# 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: TreeNode) -> int:
        self.ans = 0
        
        def preorder(root, minval, maxval):
            if not root:
                self.ans = max(self.ans, abs(minval-maxval))
                return
            
            preorder(root.left, min(minval, root.val), max(maxval, root.val))
            preorder(root.right, min(minval, root.val), max(maxval, root.val))
            
        preorder(root, float('inf'), float('-inf'))
        return self.ans

# 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: TreeNode) -> int:
        def recur(node):
            if not node:
                return (None,None,None)
            lmaxi, lmini, lres = recur(node.left)
            rmaxi, rmini, rres = recur(node.right)
            print(\"node.val\", node.val)
            print(\"lmaxi, lmini, lres\", lmaxi, lmini, lres)
            print(\" rmaxi, rmini, rres\", rmaxi, rmini, rres)
            curr = node.val
            cv = [lmaxi, lmini, rmaxi, rmini]
            res = [lres, rres]
            res = res + [abs(curr-val) for val in cv if val!=None]
            res = [val for val in res if val!=None]
            
            minr = [lmini, rmini, curr]
            maxr = [lmaxi, rmaxi, curr]
            minr = [val for val in minr if val!=None]
            maxr = [val for val in maxr if val!=None]
            
            mini = min(minr)
            maxi = max(maxr)
            print(\"res arr\", res)
            res = max([0] + res)
            print(\"node, maxi, mini, res\", node.val, maxi, mini, res)
            return (maxi, mini, res)
        _,_,res = recur(root)
        return res

# 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: TreeNode) -> int:
        self.ans = 0
        
        def preorder(root, minval, maxval):
            if not root:
                self.ans = max(self.ans, abs(minval-maxval))
                return
            
            minval, maxval = min(minval, root.val), max(maxval, root.val)
            preorder(root.left, minval, maxval)
            preorder(root.right, minval, maxval)
            
        preorder(root, float('inf'), float('-inf'))
        return self.ans

# 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: TreeNode) -> int:
        return self.helper(root)[1]
    
    def helper(self,root):
        if root == None:
            return (None,0,None) #(lowest,largest,highest)
        elif root.left == None and root.right == None:
            return (root.val,0,root.val)
        elif root.left == None:
            (r_low,r_long,r_high) = self.helper(root.right)
            return (min(r_low,root.val),max(r_long,abs(root.val - r_low ),abs(root.val - r_high)),max(r_high,root.val))
        elif root.right == None:
            (l_low,l_long,l_high) = self.helper(root.left)
            return (min(l_low,root.val),max(l_long,abs(root.val - l_low ),abs(root.val - l_high)),max(l_high,root.val))
        else:
            (r_low,r_long,r_high) = self.helper(root.right)
            (l_low,l_long,l_high) = self.helper(root.left)
            print(root,r_high,l_high,l_long,r_long)
            return (min(l_low,root.val,r_low),max(r_long,l_long,abs(root.val - min(l_low,r_low)),abs(root.val - max(r_high,l_high))),max(r_high,l_high,root.val))

# 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

# for each node
# i get:
#     left_min, right_min
#     left_max, right_max
    
# val = node.val
# current_min = min(left_min, right_min)
# current_max = max(left_max, right_max)

# max_dist = max(abs(val-current_min), abs(val-current_max))
# self.result = max(self.result, max_dist)

# return (current_min, current_max)

# after recursion return self.result


class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        
        def recurse(node):
            if node is None:
                return float('inf'), float('-inf')
            else:
                left_min, left_max = recurse(node.left)
                right_min, right_max = recurse(node.right)
                
                current_min = min(left_min, right_min)
                current_max = max(left_max, right_max)
                
                val = node.val
                
                d = 0
                if current_min != float('inf'):
                    d = max(d, abs(current_min - val))
                    
                if current_max != float('-inf'):
                    d = max(d, abs(current_max - val))
                    
                self.maxDist = max(self.maxDist, d)
                
                return min(current_min, val), max(current_max, val)
        
        self.maxDist = 0
        recurse(root)
        return self.maxDist
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        


# 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: TreeNode) -> int:
        self.ans = 0
        def traverse(node, max_v, min_v):
            self.ans = max( self.ans, abs(max_v- min_v) )
            _ = any(traverse(adj, max(max_v, adj.val), min(min_v, adj.val)) for adj in [node.left, node.right] if adj) 
        
        traverse(root, root.val, root.val)
        return self.ans


# 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:
    def maxAncestorDiff(self, root: TreeNode) -> int:

        def findMaxDiff(node, max_sf, min_sf):
            if not node:
                return float('-inf')
            cur_max = max(abs(node.val - max_sf), abs(node.val - min_sf))
            max_sf, min_sf = max(max_sf, node.val), min(min_sf, node.val)
            left_max = findMaxDiff(node.left, max_sf, min_sf)
            right_max = findMaxDiff(node.right, max_sf, min_sf)
            return max(cur_max, left_max, right_max)

        return findMaxDiff(root, root.val, root.val)        



# 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: TreeNode) -> int:
        #O(n) where n is the amount of nodes in tree
        def mdiff(root, maxval, minval):
            if not root:
                return -1
            maxval = max(root.val, maxval)
            minval = min(minval, root.val)
            return max(abs(maxval - minval), mdiff(root.left, maxval, minval), mdiff(root.right, maxval, minval))
        
        return mdiff(root, 0, 100000)

# 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, node: TreeNode) -> int:
        def helper(node, max_val, min_val):
            if not node:
                return 0
            
            diff = max(abs(max_val - node.val), abs(min_val - node.val))
            max_val = max(node.val, max_val)
            min_val = min(node.val, min_val)
            return max(helper(node.left, max_val, min_val), helper(node.right, max_val, min_val), diff)
        
        if not node:
            return 0
        
        return helper(node, node.val, node.val)

# 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: TreeNode) -> int:
        def dfs(node, path):
            if node.left == None and node.right == None: 
                if len(path) >1:
                    res[0] = max(res[0], abs(max(path) - min(path)))
                    # res[0] = max(res[0], max([abs(j - node.val) for j in path]))
                return 
            
            else:
                
                if node.left:
                    dfs(node.left, path  + [node.left.val])
                
                if node.right: 
                    dfs(node.right, path + [node.right.val])
                    
                return 
                
            
            
            
    
        res = [-1*float('infinity')]
        
        dfs(root, [root.val])
        
        # print(res)
        
        
        return res[0]

# 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: TreeNode) -> int:
        def dfs(node, path):
            if node.left == None and node.right == None: 
                if len(path) >1:
                    res[0] = max(res[0], abs(max(path) - min(path)))
                    # res[0] = max(res[0], max([abs(j - node.val) for j in path]))
                return 
            
            else:
                
                if node.left:
                    dfs(node.left, path  + [node.left.val])
                
                if node.right: 
                    dfs(node.right, path + [node.right.val])
                    
                return 
                
            
            
            
    
        res = [-1*float('infinity')]
        
        dfs(root, [root.val])
        
        print(res)
        
        
        return res[0]

# 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: TreeNode) -> int:
        
        def dfs(root: TreeNode, path: List[int]) -> None:
            if root is None:
                return
            
            path = path + [root.val]
            
            if root.left is None and root.right is None:
                result.append(path)
            else:
                dfs(root.left, path)
                dfs(root.right, path)
                    
        
        result = []
        dfs(root, path=[])
        return max([ abs(max(arr) - min(arr)) for arr in result ])

# 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

import numpy as np
class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        global_max = 0  
        
        def dfs(t):
            if t is None:
                return []
            
            lim_span_l = dfs(t.left)
            lim_span_r = dfs(t.right)

            nonlocal global_max

            lim_span = [t.val]
            if lim_span_l:
                global_max = max(global_max, np.max(np.abs(t.val - np.array(lim_span_l))))
                lim_span.extend(lim_span_l)

            if lim_span_r:
                global_max = max(global_max, np.max(np.abs(t.val - np.array(lim_span_r))))
                lim_span.extend(lim_span_r)
            
            return [min(lim_span), max(lim_span)]
        
        intv = dfs(root)
        return global_max

# 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: TreeNode) -> int:
        def dfs(node, path):
            if node.left == None and node.right == None: 
                if len(path) >1:
                    res[0] = max(res[0], abs(max(path) - min(path)))
                return 
            
            else:
                
                if node.left:
                    dfs(node.left, path  + [node.left.val])
                
                if node.right: 
                    dfs(node.right, path + [node.right.val])
                    
                return 
                    
        res = [-1*float('infinity')]
        
        dfs(root, [root.val])
        
        
        return res[0]

# 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

import numpy as np
class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.global_max = 0  
        
        def dfs(t):
            if t is None:
                return []
            
            global_max = self.global_max

            lim_span_l = dfs(t.left)
            lim_span_r = dfs(t.right)

            lim_span = [t.val]
            if lim_span_l:
                global_max = max(global_max, np.max(np.abs(t.val - np.array(lim_span_l))))
                lim_span.extend(lim_span_l)

            if lim_span_r:
                global_max = max(global_max, np.max(np.abs(t.val - np.array(lim_span_r))))
                lim_span.extend(lim_span_r)
            
            self.global_max = max(self.global_max, global_max)

            return [min(lim_span), max(lim_span)]
        
        intv = dfs(root)
        return self.global_max

# 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: TreeNode) -> int:
        def dfs(node, path):
            if node.left == None and node.right == None: 
                if len(path) >1:
                    res[0] = max(res[0], abs(max(path) - min(path)))
                return 
            
            else:
                
                if node.left:
                    dfs(node.left, path  + [node.left.val])
                
                if node.right: 
                    dfs(node.right, path + [node.right.val])
                    
                return 
                
    
        res = [-1*float('infinity')]
        
        dfs(root, [root.val])
        
        
        return res[0]

from bisect import insort
from copy import copy
# 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 traverse(self, root, path = []):
        if root is None:
            return
        
        path = copy(path)
        insort(path, root.val)
        
        if root.left is None and root.right is None:
            path_abs_diff = max(path) - min(path)
            self.max_abs_diff = max(self.max_abs_diff, path_abs_diff)

        self.traverse(root.left, path)
        self.traverse(root.right, path)
    
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.max_abs_diff = 0
        
        self.traverse(root)
        
        return self.max_abs_diff
        
        
        
                
        
            


from bisect import insort
from copy import copy
# 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 traverse(self, root, path = []):
        if root is None:
            return
        
        path = copy(path)
        insort(path, root.val)
        
        if root.left is None and root.right is None:
            path_abs_diff = path[-1] - path[0]
            self.max_abs_diff = max(self.max_abs_diff, path_abs_diff)

        self.traverse(root.left, path)
        self.traverse(root.right, path)
    
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.max_abs_diff = 0
        
        self.traverse(root)
        
        return self.max_abs_diff
        
        
        
                
        
            


# 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 traverse(self, root, path = []):
        if root is None:
            return
        
        path = path + [root.val]
        
        if root.left is None and root.right is None:
            path_abs_diff = max(path) - min(path)
            self.max_abs_diff = max(self.max_abs_diff, path_abs_diff)
        elif root.left is None:
            self.traverse(root.right, path)
        elif root.right is None:
            self.traverse(root.left, path)
        else:
            self.traverse(root.left, path)
            self.traverse(root.right, path)
    
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.max_abs_diff = 0
        
        self.traverse(root)
        
        return self.max_abs_diff
        
        
        
                
        
            


# 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: TreeNode) -> int:
        return self.recursiveMax(root, root.val, root.val)
        
    def recursiveMax(self, root, largest, smallest):
        if root is None:
            return 0
        else:
            diff1 = abs(root.val - largest)
            diff2 = abs(root.val - smallest)
            largest = max(root.val, largest)
            smallest = min(root.val, smallest)
            return max(diff1, diff2, self.recursiveMax(root.left, largest, smallest),
                      self.recursiveMax(root.right, largest, smallest))


# 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: TreeNode) -> int:
        paths=[]
        def pathsToLeafs(root,comp):
            if not root:
                return
            if not root.left and not root.right:
                paths.append(comp+[root.val])
                return
            pathsToLeafs(root.left,comp+[root.val])
            pathsToLeafs(root.right,comp+[root.val])
        pathsToLeafs(root,[])
        #now this is converted to buy and sell stock atmost one time for all paths
        def maxDiff(a):
            val=0
            n=len(a)
            dp=[0]*n
            for i in range(1,n):
                val=max(val+a[i]-a[i-1],dp[i])
                dp[i]=max(val,dp[i-1])
            return dp[-1]
                
                
        res=0
        for path in paths:
            res=max(res,maxDiff(path),maxDiff(path[::-1]))
        return res
            
            
        


# 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: TreeNode) -> int:
        \"\"\"
        IDEA: 每條path時拉出max_diff，打擂台!
        1. max_diff 查法複雜度分析：
            a. 對於一條path，最糟拉成一條:5000 * 5000 + 5000，貌似可行
                    ==> O(N^2)
            b. 優化：當path上那一顆大於我，就讓它作為 ref_value 去跟再後面的相剪
                    ==> O(N)
        \"\"\"
        \"\"\"
        ISSUES:
        1. [0,null,1], 我覺得該是 0, 但answer說是1,
            Sol, WRONG: 葉節點時，葉子自己的值也放入打擂台 X
            Sol, calc_max_diff 中，先計算diff後，如果j指的地方比i大，再把i指到j上面去
        \"\"\"
        
        if not root:
            return 0
        max_diff = [0]  # [max, min]
        # self.helper(root, [], max_diff)               # 3000 ms, 這個如果在 calc_max_diff 時不作 O(N^2) -> O(N) 的優化，就會TLE
        self.helper_early_return(root, [], max_diff)    # 220 ms
        return max(max_diff[0], 0)  # 避免所有的祖先都比子孫們都小
    
        min_max = [root.val, root.val]
        self.helper2_FAILED(root, [], max_diff, min_max)   # WRONG! 同步存儲 min_max，FAILED... 因為backtrack時得把那條路徑所貢獻的min或max放回去… 多事又麻煩
        # return res[0] - res[1]
        return min_max[1] - min_max[0]

    def helper2_FAILED(self, root, items, max_diff, min_max): # min_max at the same time
        if not root:
            # return
            # if not root.left and not root.right:
            cur_max_diff = min_max[1] - min_max[0]
            print(items, min_max)
            max_diff[0] = max(cur_max_diff, max_diff[0])
            return 
        min_max[0], min_max[1] = min(min_max[0], root.val), max(min_max[1], root.val)
        self.helper2(root.left, items + [root.val], max_diff, min_max)
        self.helper2(root.right, items + [root.val], max_diff, min_max)
    
    
    def helper(self, root, items, max_diff):
        if not root:
            cur_max_diff = self.calc_max_diff(items)
            max_diff[0] = max(cur_max_diff, max_diff[0])
            return 
            
        self.helper(root.left, items + [root.val], max_diff)
        self.helper(root.right, items + [root.val], max_diff)
    
    def helper_early_return(self, root, items, max_diff):
        if not root:
            return
        if not root.left and not root.right:
            cur_max_diff = self.calc_max_diff(items + [root.val])
            max_diff[0] = max(cur_max_diff, max_diff[0])
            return 
            
        self.helper_early_return(root.left, items + [root.val], max_diff)
        self.helper_early_return(root.right, items + [root.val], max_diff)
        
    def calc_max_diff(self, items):
        \"\"\" 8 3 6 7 
            i j
        \"\"\"
        n = len(items)
        # print(items)
        i = 0
        \"\"\" O(N) Optimization in calc_max_diff! \"\"\"
        cur_max = cur_min = items[0]
        for i in range(n):
            cur_max = max(cur_max, items[i])
            cur_min = min(cur_min, items[i])
        return cur_max-cur_min
    
        \"\"\" Orig O(N^2) calc_max_diff \"\"\"
        cur_max_diff = 0
        while i < n:
            for j in range(i+1, n):
                diff = abs(items[i] - items[j])
                cur_max_diff = max(diff, cur_max_diff)
            i += 1
        return cur_max_diff
    
#     def calc_max_diff_WRONG(self, items):   # 這是要求parent必比較大時的優化
#         \"\"\" 8 3 6 7 
#             i j
#         \"\"\"
        
#         n = len(items)
#         print(items)
#         i = 0
#         cur_max_diff = 0
#         while i < n:
#             for j in range(i+1, n):
#                 diff = items[i] - items[j]
#                 cur_max_diff = max(diff, cur_max_diff)
#                 if items[j] > items[i]:
#                     i = j
#                     # break
#                     continue

#             i += 1
#         return cur_max_diff

# 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: TreeNode) -> int:
        \"\"\"
        IDEA: 每條path時拉出max_diff，打擂台!
        1. max_diff 查法複雜度分析：
            a. 對於一條path，最糟拉成一條:5000 * 5000 + 5000，貌似可行
                    ==> O(N^2)
            b. 優化：當path上那一顆大於我，就讓它作為 ref_value 去跟再後面的相剪
                    ==> O(N)
        \"\"\"
        \"\"\"
        ISSUES:
        1. [0,null,1], 我覺得該是 0, 但answer說是1,
            Sol, WRONG: 葉節點時，葉子自己的值也放入打擂台 X
            Sol, calc_max_diff 中，先計算diff後，如果j指的地方比i大，再把i指到j上面去
        \"\"\"
        
        if not root:
            return 0
        max_diff = [0]  # [max, min]
        # self.helper(root, [], max_diff)
        self.helper_early_return(root, [], max_diff)
        return max(max_diff[0], 0)  # 避免所有的祖先都比子孫們都小
    
        min_max = [root.val, root.val]
        self.helper2_FAILED(root, [], max_diff, min_max)   # WRONG! 同步存儲 min_max，FAILED... 因為backtrack時得把那條路徑所貢獻的min或max放回去… 多事又麻煩
        # return res[0] - res[1]
        return min_max[1] - min_max[0]

    def helper2_FAILED(self, root, items, max_diff, min_max): # min_max at the same time
        if not root:
            # return
            # if not root.left and not root.right:
            cur_max_diff = min_max[1] - min_max[0]
            print(items, min_max)
            max_diff[0] = max(cur_max_diff, max_diff[0])
            return 
        min_max[0], min_max[1] = min(min_max[0], root.val), max(min_max[1], root.val)
        self.helper2(root.left, items + [root.val], max_diff, min_max)
        self.helper2(root.right, items + [root.val], max_diff, min_max)
    
    
    def helper(self, root, items, max_diff):
        if not root:
            cur_max_diff = self.calc_max_diff(items)
            max_diff[0] = max(cur_max_diff, max_diff[0])
            return 
            
        self.helper(root.left, items + [root.val], max_diff)
        self.helper(root.right, items + [root.val], max_diff)
    
    def helper_early_return(self, root, items, max_diff):
        if not root:
            return
        if not root.left and not root.right:
            cur_max_diff = self.calc_max_diff(items + [root.val])
            max_diff[0] = max(cur_max_diff, max_diff[0])
            return 
            
        self.helper_early_return(root.left, items + [root.val], max_diff)
        self.helper_early_return(root.right, items + [root.val], max_diff)
        
    def calc_max_diff(self, items):
        \"\"\" 8 3 6 7 
            i j
        \"\"\"
        n = len(items)
        # print(items)
        i = 0
        \"\"\" O(N) Optimization in calc_max_diff! \"\"\"
        cur_max = cur_min = items[0]
        for i in range(n):
            cur_max = max(cur_max, items[i])
            cur_min = min(cur_min, items[i])
        return cur_max-cur_min
    
        \"\"\" Orig O(N^2) calc_max_diff \"\"\"
        cur_max_diff = 0
        while i < n:
            for j in range(i+1, n):
                diff = abs(items[i] - items[j])
                cur_max_diff = max(diff, cur_max_diff)
            i += 1
        return cur_max_diff
    
#     def calc_max_diff_WRONG(self, items):   # 這是要求parent必比較大時的優化
#         \"\"\" 8 3 6 7 
#             i j
#         \"\"\"
        
#         n = len(items)
#         print(items)
#         i = 0
#         cur_max_diff = 0
#         while i < n:
#             for j in range(i+1, n):
#                 diff = items[i] - items[j]
#                 cur_max_diff = max(diff, cur_max_diff)
#                 if items[j] > items[i]:
#                     i = j
#                     # break
#                     continue

#             i += 1
#         return cur_max_diff

# 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: TreeNode) -> int:
        paths=[]
        def pathsToLeafs(root,comp):
            if not root:
                return
            if not root.left and not root.right:
                paths.append(comp+[root.val])
                return
            pathsToLeafs(root.left,comp+[root.val])
            pathsToLeafs(root.right,comp+[root.val])
        pathsToLeafs(root,[])
        #now this is converted to buy and sell stock atmost one time for all paths
        def maxDiff(a):
            val=0
            n=len(a)
            dp=[0]*n
            for i in range(1,n):
                val=max(val+a[i]-a[i-1],dp[i])
                dp[i]=max(val,dp[i-1])
            return dp[-1]
                
                
        res=0
        for path in paths:
            print(path)
            res=max(res,maxDiff(path),maxDiff(path[::-1]))
        return res
            
            
        


# 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 solve(self, lst, root):
        max_current = lst[-1][1]
        min_current = lst[-1][0]
        if root is not None:          
            current_value = root.val
            if current_value > max_current:
                max_current = current_value
            if current_value < min_current:
                min_current = current_value
            lst.append((min_current, max_current))
            return max(self.solve(lst[:], root.left), self.solve(lst[:], root.right))
        else:
            max_val =  max_current - min_current
            return max_val

    def maxAncestorDiff(self, root: TreeNode) -> int:
        lst = [(root.val, root.val)]
        return max(self.solve(lst[:], root.left), self.solve(lst[:], root.right))

# 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 traverse(self, root, path = []):
        if root is None:
            return
        
        path = path + [root.val]
        
        if root.left is None and root.right is None:
            path_abs_diff = max(path) - min(path)
            self.max_abs_diff = max(self.max_abs_diff, path_abs_diff)

        self.traverse(root.left, path)
        self.traverse(root.right, path)
    
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.max_abs_diff = 0
        
        self.traverse(root)
        
        return self.max_abs_diff
        
        
        
                
        
            


# 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

# do not assume binary trees are balanced or sorted!

LEFT_PROCESSED = 1
RIGHT_PROCESSED = 2

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        def recurse_func(node, parent_vals, best_answer):
            # check if we can compute a better answer with this node
            if parent_vals:
                ans = abs(min(parent_vals) - node.val)
                if ans > best_answer:
                    best_answer = ans
                ans = abs(max(parent_vals) - node.val)
                if ans > best_answer:
                    best_answer = ans
            
            # check our children
            # there is some optimization that can occur here to prune entire branches if we detect the best answer is larger
            # than the largest value we expect to find in the tree branch, but we would need to record whether we came down the left or right branch of the parent
            parent_vals.append(node.val)
            if node.left:
                best_answer = recurse_func(node.left, parent_vals, best_answer)
            if node.right:
                best_answer = recurse_func(node.right, parent_vals, best_answer)
            parent_vals.pop()
            
            # return best_answer
            return best_answer
    
        return recurse_func(root, [], 0)

    
#         best_answer = 0
#         parent_nodes = [[root, 0]]
#         while parent_nodes:
#             cn = parent_nodes[-1]
#             for n in parent_nodes:
#                 ans = abs(n[0].val - cn[0].val)
#                 if ans > best_answer:
#                     best_answer = ans

#             n = cn[0]                    
#             if not (cn[1] & LEFT_PROCESSED):
#                 cn[1] = cn[1] | LEFT_PROCESSED
#                 if n.left:
#                     parent_nodes.append([n.left, 0])
#                 continue
#             if not (cn[1] & RIGHT_PROCESSED):
#                 cn[1] = cn[1] | RIGHT_PROCESSED
#                 if n.right:
#                     parent_nodes.append([n.right, 0])
#                 continue
#             if (cn[1] & LEFT_PROCESSED) and (cn[1] & RIGHT_PROCESSED):
#                 parent_nodes.pop()
#         return best_answer
        
    
                


# 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: TreeNode) -> int:
        
        maximum = -float(\"inf\")
        stack = []
        def dfs(root):
            nonlocal maximum
            if not root:
                maximum = max(abs(max(stack) - min(stack)), maximum)
                return
            stack.append(root.val)
            dfs(root.left)
            dfs(root.right)
            stack.pop()
        dfs(root)
        return maximum
            
        

# 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: TreeNode) -> int:
        self.v_max = 0
        
        def find(node, path):
            if not node:                
                return 
 
            tmp = max(abs(max(path) - node.val), abs(min(path) - node.val))
            self.v_max = max(self.v_max, tmp)
            
            path.append(node.val)
            
            find(node.left, path)
            find(node.right, path)
            
            path.pop()
            
        find(root, [root.val])
        return self.v_max

# 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: TreeNode) -> int:
        if not root:
            return 0
        stack = [(root,root.val,root.val)]
        maxDiff = -1
        while stack:
            node, maxVal, minVal = stack.pop()
            maxVal = max(maxVal,node.val)
            minVal = min(minVal,node.val)
            maxDiff = max(maxDiff,maxVal-minVal)
            if node.left:
                stack.append((node.left,maxVal,minVal))
            if node.right:
                stack.append((node.right,maxVal,minVal))
        return maxDiff

# 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:
    maxDiff = 0
    def maxAncestorDiff(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        currPath = []
        
        def dfs(currNode, currPath):
            currPath.append(currNode.val)
            
            if currNode.left:
                dfs(currNode.left, currPath)
                
            if currNode.right:
                dfs(currNode.right, currPath)
                
            self.maxDiff = max(self.maxDiff, max(currPath) - min(currPath))
        
            currPath.pop()
        
        dfs(root, currPath)
        return self.maxDiff

# 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:
    maxDiff = 0
    def maxAncestorDiff(self, root: TreeNode) -> int:
        currPath = []
        
        def dfs(currNode, currPath):
            if not currNode:
                if len(currPath) > 0:
                    self.maxDiff = max(self.maxDiff, max(currPath) - min(currPath))
                    
                return
            
            currPath.append(currNode.val)
            
            dfs(currNode.left, currPath)
            dfs(currNode.right, currPath)
                
            currPath.pop()
        
        dfs(root, currPath)
        return self.maxDiff

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

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.mx=0
        path=[]
        def getpath(root):
            if not root:
                return
            path.append(root.val)
            if len(path)>1:
                self.mx=max(self.mx,abs(min(path[:-1])-path[-1]))
                self.mx=max(self.mx,abs(max(path[:-1])-path[-1]))
                #print(path)
            getpath(root.left)
            getpath(root.right)
            path.pop()
            
        getpath(root)
        return self.mx

# 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: TreeNode) -> int:
        self.max_diff = -float('inf')
        self.dfs(root, [])
        return self.max_diff

    def dfs(self, root, path):
        if not root:
            # print(path)
            self.max_diff = max(self.max_diff, max(path) - min(path))
            return
        self.dfs(root.left, path + [root.val])
        self.dfs(root.right, path + [root.val])

# 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: TreeNode) -> int:
        self.maxval = float('-inf')
        def dfs(node, ans):
            if node:
                if ans:
                    self.maxval = max(self.maxval, abs(max(ans) - node.val))
                    self.maxval = max(self.maxval, abs(min(ans) - node.val))
                
                dfs(node.left, ans + [node.val])
                dfs(node.right, ans + [node.val])
        dfs(root, [])
        return self.maxval


# 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: TreeNode) -> int:
        self.max_diff = -float('inf')
        self.dfs(root, [])
        return self.max_diff

    def dfs(self, root, path):
        if not root:
            self.max_diff = max(self.max_diff, max(path) - min(path))
            return
        self.dfs(root.left, path + [root.val])
        self.dfs(root.right, path + [root.val])

# 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: TreeNode) -> int:
        def traverse(root, prev_min, prev_max):
            if root:
                prev_min = min(root.val, prev_min)
                prev_max = max(root.val, prev_max)
                return max(traverse(root.left, prev_min, prev_max), traverse(root.right, prev_min, prev_max))
            else:
                return prev_max - prev_min

        return traverse(root, root.val, root.val)

# 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: TreeNode) -> int:
        self.res = float(-inf)
        self.dfs(root, [])
        
        return self.res
    
    def dfs(self, node, path):
        if not node:
            self.res = max(self.res, max(path) - min(path))
            return
        
        self.dfs(node.left, path+[node.val])
        self.dfs(node.right, path+[node.val])


# 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: TreeNode) -> int:
        # initialize a difference variable for the difference value
        # have to account for if max is a negative number. 0 is > -num
        self.max_diff = -float(\"inf\")
        # call helper function passing in the root (where you start) and an empty list [] (holds the path of travel)
        self.dfs(root, [])
        
        # return out the max difference value
        return self.max_diff
    
    # helper method to track path and perform subtraction
    def dfs(self, root, path):
        # if there is not root
        if not root:
            # print(\"PATH: \", path)
            self.max_diff = max(self.max_diff, max(path) - min(path))
            return
        self.dfs(root.left, path + [root.val])
        self.dfs(root.right, path + [root.val])
        

# 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: TreeNode) -> int:
        self.max_diff = -float('inf')
        
        def helper(node, vals):
            
            if not node:
                self.max_diff = max(self.max_diff,abs(max(vals)-min(vals)))
                return 
            
            helper(node.left,vals + [node.val])
            helper(node.right,vals + [node.val])
                
        helper(root, [root.val])
        
        return self.max_diff
                


# 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: TreeNode) -> int:
        self.dist = 0

        def dfs(node, ancesVal):
            #print(ancesVal)
            if not node:
                self.dist = max(self.dist, abs(max(ancesVal) -  min(ancesVal)))
                return
            
            dfs(node.left, ancesVal + [node.val])

            dfs(node.right, ancesVal + [node.val])
            return 
      
        dfs(root, [])
        return self.dist

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

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        
        ##### Using dfs and finding diff of min and max values
        self.mx=0
        path=[]
        def getpath(root):
            if not root:
                return
            path.append(root.val)
            self.mx=max(self.mx,abs(min(path)-max(path)))
            #print(path)
            getpath(root.left)
            getpath(root.right)
            path.pop()
            
        getpath(root)
        return self.mx
       
                    
                    


# 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: TreeNode) -> int:
        self.max_diff = -float('inf')
        self.dfs(root, [], [])
        return self.max_diff

    def dfs(self, root, path, res):
        if not root:
            # print(path)
            self.max_diff = max(self.max_diff, max(path) - min(path))
            return
        self.dfs(root.left, path + [root.val], res)
        self.dfs(root.right, path + [root.val], res)

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.max_diff = -float('inf')
        self.dfs(root, [])
        return self.max_diff

    def dfs(self, root, path):
        if not root:
            # print(path)
            self.max_diff = max(self.max_diff, max(path) - min(path))
            return
        self.dfs(root.left, path + [root.val])
        self.dfs(root.right, path + [root.val])

# 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: TreeNode) -> int:
        return self.recursiveMax(root, root.val, root.val, 0)
        
    def recursiveMax(self, root, largest, smallest, max_so_far):
        if root is None:
            return max_so_far
        else:
            diff1 = abs(root.val - largest)
            diff2 = abs(root.val - smallest)
            largest = max(root.val, largest)
            smallest = min(root.val, smallest)
            max_so_far = max(max_so_far, diff1, diff2)
            return max(max_so_far, self.recursiveMax(root.left, largest, smallest, max_so_far),
                      self.recursiveMax(root.right, largest, smallest, max_so_far))


# 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: TreeNode) -> int:
        self.max_diff = 0
        self.dfs(root, [])
        return self.max_diff

    def dfs(self, root, path):
        if not root:
            # print(path)
            self.max_diff = max(self.max_diff, max(path) - min(path))
            return
        self.dfs(root.left, path + [root.val])
        self.dfs(root.right, path + [root.val])


# 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: TreeNode) -> int:
        stack = [[root, [root.val]]]
        res = 0
        while stack:
            node, ancestors = stack[0]
            res = max(res, abs(node.val - ancestors[0]), abs(node.val - ancestors[-1]))
            for i in range(len(ancestors)):
                if node.val >= ancestors[i]:
                    new_ancestors = ancestors[0:i] + [node.val] + ancestors[i:]
                    break 
                if i == len(ancestors) - 1:
                    new_ancestors = ancestors + [node.val]
            if node.left != None:
                stack.append([node.left, new_ancestors])
            if node.right != None:
                stack.append([node.right, new_ancestors])
            stack = stack[1:]
        return(res)

# 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: TreeNode) -> int:
        maxDiff = 0
        stk = [root]
        ancDict = {}
        ancDict[root.val] = []
        while len(stk)!=0:
            root = stk.pop()
            if root.left is not None:
                stk.append(root.left)
                if root.left not in ancDict:
                    ancDict[root.left.val] = []
                ancDict[root.left.val].append(root.val)
                ancDict[root.left.val].extend(ancDict[root.val])
            if root.right is not None:
                stk.append(root.right)
                if root.right not in ancDict:
                    ancDict[root.right.val] = []
                ancDict[root.right.val].append(root.val)
                ancDict[root.right.val].extend(ancDict[root.val])
        for k in ancDict:
            for v in ancDict[k]:
                if abs(v - k) > maxDiff:
                    maxDiff = abs(v - k)
        return maxDiff

# 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

import queue
from collections import defaultdict
class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        maxDiff = 0
        dq = queue.deque()
        dq.append(root)
        data = []
        nodes = defaultdict(list)
        
        while any(dq):
            node = dq.popleft()
            data.append(node.val)
            if node.left:
                dq.append(node.left)
                nodes[node.left.val].append(node.val)
                nodes[node.left.val].extend(nodes[node.val])
            if node.right:
                dq.append(node.right)
                nodes[node.right.val].append(node.val)
                nodes[node.right.val].extend(nodes[node.val])
        for key, value in list(nodes.items()):
            if not value: continue
            s = 0
            for val in value:
                if abs(key-val) > s:
                    s = abs(key-val)
            if s > maxDiff:
                maxDiff = s
                
        return maxDiff
        
                
                
            
            
            
            
            


# 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: TreeNode) -> int:
        self.ans = -1
        
        def solve(r: TreeNode, ancestors: List[int]):
            if r is None:
                return
            
            # print(f'{ancestors} {r.val}')
            v = r.val
            if len(ancestors) > 0:
                tmp = max([abs(a - v) for a in ancestors])
                self.ans = max(tmp, self.ans)
                
            ancestors.append(v)
            solve(r.left, ancestors)
            solve(r.right, ancestors)
            ancestors.pop()
        
        solve(root, [])
        return self.ans

# 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

def calculateDifference(root,parent):
    maxi = 0
    for i in parent:
        if abs(root.val-i) > maxi:
            maxi = abs(root.val-i)
    if root.left:
        maxi = max(maxi,calculateDifference(root.left,parent+[root.val]))
    if root.right:
        maxi = max(maxi,calculateDifference(root.right,parent+[root.val]))
        
    return maxi


class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        if root is None:
            return 0
        
        
        return calculateDifference(root,[])


# 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: TreeNode) -> int:
        
        def recAncestors(root, ancestors,dif):
            left_dif=0
            right_dif=0
            for node in ancestors:
                if dif<abs(root.val-node):
                    dif=abs(root.val-node)
            father=ancestors+[root.val]
            if root.left:
                left_dif=recAncestors(root.left,father,dif)
            if root.right:
                right_dif=recAncestors(root.right,father,dif)
            return max(left_dif,right_dif,dif)        
        nodes=[root.val]
        right_wing, left_wing = 0,0
        if root.right:
            right_wing=recAncestors(root.right, nodes ,0)
        if root.left:
            left_wing=recAncestors(root.left,nodes,0)
        return max(right_wing,left_wing)
            


# 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: TreeNode) -> int:
        # Walk the tree
        
        def recurse_func(node, parent_vals, best_answer):
            # check if we can compute a better answer with this node
            for x in parent_vals:
                ans = abs(x - node.val)
                if ans > best_answer:
                    best_answer = ans
            
            # check our children
            # there is some optimization that can occur here to prune entire branches if we detect the best answer is larger
            # than the largest value we expect to find in the tree branch, but we would need to record whether we came down the left or right branch of the parent
            parent_vals.append(node.val)
            if node.left:
                best_answer = recurse_func(node.left, parent_vals, best_answer)
            if node.right:
                best_answer = recurse_func(node.right, parent_vals, best_answer)
            parent_vals.pop()
            
            # return best_answer
            return best_answer
    
        return recurse_func(root, [], 0)
    
                    
                


# 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: TreeNode) -> int:
        
        
        def traverse(root,anc,diff):
            
            if root:
                for an in anc:
                    if abs(root.val-an)>diff:
                        diff=abs(root.val-an)                
                
                diff=traverse(root.left,anc+[root.val],diff)
                diff=traverse(root.right,anc+[root.val],diff)
     
            return diff

        return traverse(root,[],0)

# 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: TreeNode) -> int:
        
        def maxDiff(root, ancestors):
            if root is None:
                return 0
            
            maxRightHere = 0
            for ancestor in ancestors:
                difference = abs(ancestor - root.val)
                if difference > maxRightHere:
                    maxRightHere = difference
            
            ancestors.append(root.val)
            maxLeft = maxDiff(root.left, ancestors)
            
            maxRight = maxDiff(root.right, ancestors)
            ancestors.pop()
            
            return max(maxRightHere, maxLeft, maxRight)
        
        return maxDiff(root, [])

# 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


from dataclasses import dataclass

MIN_VALUE = -2**31
MAX_VALUE = 2**31


@dataclass
class State:
    min_: int
    max_: int
    val: int


def max_ancestor_diff(root: TreeNode) -> State:
    if not root:
        return State(MAX_VALUE, MIN_VALUE, 0)
    
    left = max_ancestor_diff(root.left)
    right = max_ancestor_diff(root.right)
    
    min_ = min(left.min_, right.min_, root.val)
    max_ = max(left.max_, right.max_, root.val)
    val = max(left.val, right.val, max_ - root.val, root.val - min_)
    return State(min_, max_, val)
    

class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        return max_ancestor_diff(root).val


# 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: TreeNode) -> int:
        if not root:
            return 0
        
        maxDiff = 0
        def dfs(node):
            if not node:
                return []
            
            vals = dfs(node.left)
            vals.extend(dfs(node.right))
            
            nonlocal maxDiff
            localMaxDiff = max([abs(v - node.val) for v in vals]) if vals else 0            
            maxDiff = max(maxDiff, localMaxDiff)
            vals.append(node.val)
            return vals
        
        dfs(root)
        return maxDiff


# 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: TreeNode) -> int:
        #DFS
        stack = [(root, [])]
        maxDiff = 0
        while stack:
            node, anc = stack.pop()
            if anc:
                maxDiff = max(maxDiff, 
                         max(abs(node.val - v) for v in anc))
            if node.left:
                stack.append((node.left, anc + [node.val]))
            if node.right:
                stack.append((node.right, anc + [node.val]))
        return maxDiff

# 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 helper(self,root,output,maxValue):
        if(root is None):
            return 
        for ele in output:
            if(abs(root.val-ele)>maxValue[0]):
                maxValue[0]=abs(root.val-ele)
        # if(len(output)>1):
        #     ele1=output[-1]
        #     ele2=output[-2]
        #     if(abs(root.val-ele1)>maxValue[0]):
        #         maxValue[0]=abs(root.val-ele1)
        #     if(abs(root.val-ele2)>maxValue[0]):
        #         maxValue[0]=abs(root.val-ele2)
        # elif(len(output)==1):
        #     ele1=output[-1]
            # if(abs(root.val-ele1)>maxValue[0]):
            #     maxValue[0]=abs(root.val-ele1)
        output.append(root.val)
        self.helper(root.left,output,maxValue)
        self.helper(root.right,output,maxValue)
        output.pop()
    def maxAncestorDiff(self, root: TreeNode) -> int:
        maxValue=[0]
        output=list()
        self.helper(root,output,maxValue)
        return maxValue[0]


# 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: TreeNode) -> int:
        def dfs(node, path):
            if node.left == None and node.right == None: 
                res[0] = max(res[0], max([abs(j - node.val) for j in path]))
                return 
            
            else:
                if len(path)>0:
                    res[0] = max(res[0], max([abs(j - node.val) for j in path]))
                
                if node.left:
                    dfs(node.left, path  + [node.val])
                
                if node.right: 
                    dfs(node.right, path + [node.val])
                    
                return 
                
            
            
            
    
        res = [-1*float('infinity')]
        
        dfs(root, [])
        
        print(res)
        
        
        return res[0]

# 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 __init__(self):
        self.max_diff = -1
    
    def maxAncestorDiff(self, root: TreeNode) -> int:
        
        def max_diff_calc(root):
            if not root:
                return []
            ancestors = max_diff_calc(root.left)
            ancestors.extend(max_diff_calc(root.right))
            for ans in ancestors:
                if abs(root.val - ans) > self.max_diff:
                    self.max_diff = abs(root.val - ans)
            ancestors.append(root.val)
            return ancestors
        
        max_diff_calc(root)
        return self.max_diff

# 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: TreeNode) -> int:
        
        res = 0
        if not root:
            return 
        
        def dfs(node, a):
            nonlocal res          
            tmp = max(abs(x-node.val) for x in a) if a else 0
            res = max(res, tmp)
            if node.left:
                a.append(node.left.val)
                dfs(node.left, a)#;print('111', node.left.val, a)
                a.pop()
            if node.right:
                a.append(node.right.val)
                dfs(node.right, a) #;print('222', node.right.val, a)
                a.pop()
            return
        
        dfs(root, [root.val])
        return res

# 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: TreeNode) -> int:
        def tranverse(node, ansestors, res):
          res = max(
            res,
            max([
              abs(val - node.val)
              for val in ansestors
            ]) if ansestors else 0,
          )
          ansestors.append(node.val)
          
          if node.left:
            res = tranverse(node.left, ansestors, res)
          
          if node.right:
            res = tranverse(node.right, ansestors, res)
          
          ansestors.pop()
          return res
        
        return tranverse(root, [], 0)

# 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 helper(self, root, path, ans):
        if not root:
            return
        if path:
            ans[0] = max(ans[0], max([abs(root.val-x) for x in path]))
        path.append(root.val)
        self.helper(root.left, path.copy(), ans)
        self.helper(root.right, path.copy(), ans)

    def maxAncestorDiff(self, root: TreeNode) -> int:
        ans = [-float('inf')]
        self.helper(root, [], ans)
        return ans[0]


# 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: TreeNode) -> int:
        return(self.helper(root)[1])
    
    def helper(self,root,myMax=0):
        myList = []
        if root.left:
            temp1,temp2 = self.helper(root.left)
            myList.extend(temp1)
            if temp2 > myMax:
                myMax = temp2
        if root.right:
            temp1,temp2 = self.helper(root.right)
            myList.extend(temp1)
            if temp2 > myMax:
                myMax = temp2
        myList.append(root.val)
        for i in range(len(myList)-1):
            if abs(root.val - myList[i]) > myMax:
                myMax = abs(root.val - myList[i])
        return (myList,myMax)

# 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(object):
    res = 0
    
    def dfs(self, root):
        if not root:
            return (0, 0)        
        if not root.left and not root.right:
            return (root.val, root.val)        
        left_min = right_min = float('inf')
        left_max = right_max = float('-inf')
        if root.left:
            left_min, left_max = self.dfs(root.left)        
        if root.right:
            right_min, right_max = self.dfs(root.right)
        min_val = min(left_min, right_min)
        max_val = max(left_max, right_max)        
        self.res = max(self.res, abs(root.val - min_val), abs(root.val - max_val))
        return (min(min_val, root.val), max(max_val, root.val))
    
    def maxAncestorDiff(self, root):
        \"\"\"
        :type root: TreeNode
        :rtype: int
        \"\"\"
        self.dfs(root)        
        return self.res
    

# 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: TreeNode) -> int:
        best = {0:-1}
        def maxmin(root,path):
            if root == None:
                return 200000
            else:
                best[0] = max(best[0],max([0]+[abs(root.val-val) for val in path]))
                maxmin(root.left,path+[root.val])    
                maxmin(root.right,path+[root.val])
        maxmin(root,[])
        return best[0]

# 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: TreeNode) -> int:
        
        if not root or not root.left and not root.right:
            return 0
        self.max_val = 0
        self.traverseWithAncestor(root, [])
        
        
        return self.max_val
    
    def traverseWithAncestor(self, root, ancestors):

        # base case
        if not root:
            return 
    
        for v in ancestors:
            if (res := abs(root.val-v)) > self.max_val:
                self.max_val = res
        
        if not root.left and not root.right:
            return
        
        newAncestors = list(ancestors)
        newAncestors.append(root.val)
        if root.left:
            self.traverseWithAncestor(root.left, newAncestors)
        if root.right:
            self.traverseWithAncestor(root.right, newAncestors)

# 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: TreeNode) -> int:
        
        if not root or not root.left and not root.right:
            return 0
        self.max_val = 0
        self.traverseWithAncestor(root, [])
        
        
        return self.max_val
    
    def traverseWithAncestor(self, root, ancestors):

        # base case
        if not root:
            return 
    
        for v in ancestors:
            if (res := abs(root.val-v)) > self.max_val:
                self.max_val = res
        
        if not root.left and not root.right:
            return
        
        newAncestors = list(ancestors)
        newAncestors.append(root.val)
        self.traverseWithAncestor(root.left, newAncestors)
        self.traverseWithAncestor(root.right, newAncestors)

# 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:
    # pairs = []
    abs_max = -99999
    
    def construct_all_pairs(self, subtree):
        if subtree is None:
            return []
        else:
            lp = self.construct_all_pairs(subtree.left)
            rp = self.construct_all_pairs(subtree.right)
            for l in lp:
                # self.pairs.append((subtree.val, l))
                if abs(subtree.val - l) > self.abs_max:
                    self.abs_max = abs(subtree.val - l)
            for r in rp:
                # self.pairs.append((subtree.val, r))
                if abs(subtree.val - r) > self.abs_max:
                    self.abs_max = abs(subtree.val - r)
            return [subtree.val] + lp + rp
        
    
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.construct_all_pairs(root)
        return self.abs_max
        # print(self.pairs)
        # return max(map(lambda x : abs(x[0]-x[1]) , self.pairs))


# 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:
    ans = 0
    def maxAncestorDiff(self, root: TreeNode) -> int:
        def visit(root, ancs):
            if root is None: return
            if ancs:
                self.ans = max(self.ans, max(abs(root.val - o) for o in ancs))
            visit(root.left, ancs+[root.val])
            visit(root.right, ancs+[root.val])
            
        visit(root, [])
        return self.ans

# 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: TreeNode) -> int:
        if not root:
            return 0
        
        def maxDiff(root: TreeNode, ancestors: List[int]) -> int:
            if not root:
                return 0
            
            left_max = maxDiff(root.left, ancestors + [root.val])
            right_max = maxDiff(root.right, ancestors + [root.val])
            diffs = [abs(ancestor - root.val) for ancestor in ancestors]
            return max(diffs + [left_max, right_max])
        
        return maxDiff(root, [])

# 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: TreeNode) -> int:
        self.mx = 0
        def dfs(node, visited):
            if node is None:
                return
            else:
                for v in visited:
                    if abs(v-node.val) > self.mx:
                        self.mx = abs(v-node.val)
            dfs(node.left, visited+[node.val])
            dfs(node.right, visited+[node.val])
            return
        dfs(root, [])
        return self.mx

# 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 dfs(self, root, ancestors):
        if ancestors:
            for anc in ancestors:
                potential = abs(root.val - anc)
                if potential > self.ans:
                    self.ans = potential 
        
        if root.left:
            self.dfs(root.left, ancestors + [root.val])
        if root.right:
            self.dfs(root.right, ancestors + [root.val])
    
    
    def maxAncestorDiff(self, root: TreeNode) -> int:
        self.ans = 0
        self.dfs(root, [])
        return self.ans

# 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: TreeNode) -> int:
        self.max_val = 0
        
        def traversal(root,parent):

            if not root:
                return
            for i in parent:
                
                if self.max_val < abs(i-root.val):
                    self.max_val = abs(i-root.val)
            if root.left:
                traversal(root.left,parent+[root.val])
            if root.right:
                traversal(root.right,parent+[root.val])
            return
        traversal(root,[]) 
        return self.max_val

# 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: TreeNode) -> int:
        
        self.max_d = 0
        def get_distance_list(node, dist_list):
            dist_list_new = []
            if not (node.left or node.right):
                return [0]
            else:
                if node.left:
                    dist_list_l = get_distance_list(node.left, dist_list)
                    diff_l = node.val - node.left.val
                    dist_list_l = [d+diff_l for d in dist_list_l]
                    dist_list_new += dist_list_l
                    dist_list_new.append(diff_l)
                if node.right:
                    dist_list_r = get_distance_list(node.right, dist_list)
                    diff_r = node.val - node.right.val
                    dist_list_r = [d+diff_r for d in dist_list_r]
                    dist_list_new += dist_list_r
                    dist_list_new.append(diff_r)
            for d in dist_list_new:
                if abs(d)>self.max_d:
                    self.max_d = abs(d)
            return dist_list_new
        
        get_distance_list(root, [])
        return self.max_d
                
                


# 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: TreeNode) -> int:
        # Use DFS, and a max diff tracker.
        # Each node has a min-max ancestor.
        # Time: O(N), Space: O(log(N))
        self.max_p_diff = 0
        def max_diff(node, p_min, p_max):
            if not node:
                return
            self.max_p_diff = max(self.max_p_diff, max(abs(node.val-p_min), abs(p_max-node.val)))
            p_min = min(node.val, p_min)
            p_max = max(node.val, p_max)
            max_diff(node.left, p_min, p_max)
            max_diff(node.right, p_min, p_max)
        max_diff(root, root.val, root.val)
        return self.max_p_diff


# 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: TreeNode) -> int:
        def util(root, maxDiff):
            if not root:
                return [], maxDiff
            lArr, maxDiff = util(root.left, maxDiff)
            rArr, maxDiff = util(root.right, maxDiff)
            
            for node in lArr:
                if abs(root.val - node.val) > maxDiff:
                    maxDiff = abs(root.val - node.val)
            for node in rArr:
                if abs(root.val - node.val) > maxDiff:
                    maxDiff = abs(root.val - node.val)
            return [root] + lArr + rArr, maxDiff
        arr, maxDiff = util(root, float('-inf'))
        return maxDiff

# 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: TreeNode) -> int:
        
        def dfs(root: TreeNode, ancestors_values) -> int:
            
            result = [-1]
            this_ancestors_values = [root.val] + ancestors_values
            
            if root.left is not None:
                max_ancestors_diff = max([abs(a - root.left.val) for a in this_ancestors_values])
                left_result = dfs(root.left, this_ancestors_values)
                left_result = max(left_result, max_ancestors_diff)
                result.append(left_result)
            if root.right is not None:
                max_ancestors_diff = max([abs(a - root.right.val) for a in this_ancestors_values])
                right_result = dfs(root.right, this_ancestors_values)
                right_result = max(right_result, max_ancestors_diff)
                result.append(right_result)
            
            return max(result)
            
        result = dfs(root, [])
        return result


# 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: TreeNode) -> int:
        if not root:
            return 0
        
        stack=[root]
        parent={root:None}
        while stack:
            p=stack.pop()
            if p.right:
                stack.append(p.right)
                parent[p.right]=p
            if p.left:
                stack.append(p.left)
                parent[p.left]=p
        
        ans=0
        for nodes in parent:
            res=[]
            while nodes:
                res.append(nodes.val)
                nodes=parent[nodes]
            ans=max(ans,max(res)-min(res))
        
        return ans

from typing import List


# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

#     def __repr__(self):
#         return str(self.val)


class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        return max_ancestor_diff(root, [])


def max_ancestor_diff(node: TreeNode, lineage: List[TreeNode]) -> int:
    if node is None:
        return 0

    if lineage:
        max_diff = max([abs(node.val - n.val) for n in lineage])
    else:
        max_diff = 0

    if node.left is not None:
        max_diff = max(max_diff, max_ancestor_diff(
            node.left, lineage + [node]))

    if node.right is not None:
        max_diff = max(max_diff, max_ancestor_diff(
            node.right, lineage + [node]))

    return max_diff


# 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: TreeNode) -> int:
        deque = collections.deque([[root, []]])
        result = 0
        while deque:
            node, anc = deque.popleft()
            max_abs = 0 if not len(anc) else max(abs(node.val - a.val) for a in anc)
            result = max(result, max_abs)
            if node.left:
                deque.append([node.left, anc + [node]])
            if node.right:
                deque.append([node.right, anc + [node]])
        return result

# 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: TreeNode) -> int:
        def dfs(root):
            if root:
                vals.add(root.val)
                dfs(root.left)
                dfs(root.right)
                
        def dfs2(root, anss):
            if root:
                for a in anss:
                    v = abs(a-root.val)
                    if v in vals and v > self.ans:
                        self.ans = v
                dfs2(root.left, anss+[root.val])
                dfs2(root.right, anss+[root.val])
                
        vals = set()
        dfs(root)
        self.ans = float(\"-inf\")
        dfs2(root, [])
        return self.ans
        

# 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: TreeNode) -> int:
        # Map each node with a list of its ancestors
        # We can do that by iterating with DFS and path
        
        q = [(root, [])]
        
        from collections import defaultdict
        
        anc = {}
        
        while q: 
            cur, path = q.pop(0)
            
            
            anc[cur.val] = path
            
            path.append(cur.val)
            
            if cur.left: 
                q.append((cur.left, path[:]))
            
            if cur.right: 
                q.append((cur.right, path[:]))
                
        
        max_diff = float('-inf')
        
        for n, ancs in list(anc.items()):
            for a in ancs: 
                max_diff = max(max_diff, abs(a - n))
                
        
        return max_diff


# 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: TreeNode) -> int:
        # Map each node with a list of its ancestors
        # We can do that by iterating with DFS and path
        
        q = [(root, [])]
        
        from collections import defaultdict
        
        anc = {}
        
        while q: 
            cur, path = q.pop(0)
            
            
            anc[cur.val] = path[:]
            
            path.append(cur.val)
            
            if cur.left: 
                q.append((cur.left, path[:]))
            
            if cur.right: 
                q.append((cur.right, path[:]))
                
        
        max_diff = float('-inf')
        
        for n, ancs in list(anc.items()):
            for a in ancs: 
                max_diff = max(max_diff, abs(a - n))
                
        
        return max_diff


from typing import List
from functools import lru_cache


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return str(self.val)


class Solution:
    def maxAncestorDiff(self, root: TreeNode) -> int:
        return max_ancestor_diff(root, [])


@lru_cache
def get_max_lineage_diff(node: TreeNode, lineage) -> int:
    if lineage:
        return max([abs(node.val - n.val) for n in lineage])
    else:
        return 0


def max_ancestor_diff(node: TreeNode, lineage: List[TreeNode]) -> int:
    if node is None:
        return 0

    max_diff = get_max_lineage_diff(node, frozenset(lineage))

    if node.left is not None:
        max_diff = max(max_diff, max_ancestor_diff(
            node.left, lineage + [node]))

    if node.right is not None:
        max_diff = max(max_diff, max_ancestor_diff(
            node.right, lineage + [node]))

    return max_diff


# 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: TreeNode) -> int:
        return self.maxAncestorDiffHelper(root, [], 0)
    
    def maxAncestorDiffHelper(self, root: TreeNode, ancestors, maxV: int) -> int:
        if root is None:
            return 0
        for a in ancestors:
            maxV = max(maxV, abs(a-root.val))
        ancestors.append(root.val)
        maxV = max(
            maxV,
            self.maxAncestorDiffHelper(root.left, ancestors, maxV),
            self.maxAncestorDiffHelper(root.right, ancestors, maxV)
        )
        ancestors.pop()
        return maxV
    
    #TODO should be able to make this faster