1026. Maximum Difference Between Node and Ancestor

Comments

Problem Setting

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.)

Note:

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

Example 1

Input: [8,3,10,1,6,null,14,null,null,4,7,13]

Example 1

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.

Solution

Solution 1 from superluminal

In [1]:
class Solution(object):
    def maxAncestorDiff(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        r = [0]
        def f(node, a, b):
            if not node: return
            r[0] = max(r[0], abs(node.val-a), abs(node.val-b))
            a = min(a, node.val)
            b = max(b, node.val)
            f(node.left, a, b)
            f(node.right, a, b)
        f(root, root.val, root.val)
        return r[0]

Step-by-step

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

class Solution(object):
    def maxAncestorDiff(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        r = [0]
        def f(node, a, b):
            if not node: return
            r[0] = max(r[0], abs(node.val-a), abs(node.val-b))
            a = min(a, node.val)
            b = max(b, node.val)
            f(node.left, a, b)
            f(node.right, a, b)
        f(root, root.val, root.val)
        return r[0]

Execute the entire class

In [4]:
# Execute the entire class
root = TreeNode(1)
root.left = TreeNode(3)
root.left.left = TreeNode(5)
root.right = TreeNode(2)

s = Solution()
s.maxAncestorDiff(root)
Out[4]:
4

Execute recursive function f

a and b stores the minimum and maximum value across calculation. r[0] is the result value, which is compared with the absolute distance between the value at the current node and the minimum or maximum in the ancestor path. Then, recursively this function f is called and stores the maximum of absolute distance in the ancestor path.

I noticed that r[0] is actually not necessarily to be a list. It can be just a value.

In [14]:
def f(node, a, b):
    if not node: return
    print('Processing at {}'.format(node.val))
    print('Compare {}, {}, {}'.format(r[0], abs(node.val-a), abs(node.val-b)))
    r[0] = max(r[0], abs(node.val-a), abs(node.val-b))
    print('Updated the maximum distance to {}'.format(r[0]))
    a = min(a, node.val)
    b = max(b, node.val)
    f(node.left, a, b)
    f(node.right, a, b)

The example of f execution as below returns 4 between the root for 1 and the left bottom node for 5.

(root)               
          (1)                                                    
         / \                                                  
        3   2                                            
       /                                               
      (5)
In [15]:
r = [0]
f(root, root.val, root.val)

Processing at 1
Compare 0, 0, 0
Updated the maximum distance to 0
Processing at 3
Compare 0, 2, 2
Updated the maximum distance to 2
Processing at 5
Compare 2, 4, 2
Updated the maximum distance to 4
Processing at 2
Compare 4, 1, 1
Updated the maximum distance to 4
In [8]:
# Result is 4 between node 1 and 5
r
Out[8]:
[4]

Solution 2 from badgergo

This is essentially the same as the above. The key is to create the recursive function for depth first search to keep minimum and maximum values across ancestor path.

In [ ]:
# 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:
        def dfs(node, mn=math.inf, mx=-math.inf):
            if node:
                mn = min(mn, node.val)
                mx = max(mx, node.val)
                dfs(node.left, mn, mx)
                dfs(node.right, mn, mx)
            else:
                self.ans = max(self.ans, mx - mn)
        self.ans = 0
        dfs(root)
        return self.ans

Comments

Comments powered by Disqus