Algorithm
Problem Name: 1026. Maximum Difference Between Node and Ancestor
Given the root of a binary tree, find the maximum value v for which there exist 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: root = [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.
Example 2:
Input: root = [1,null,2,null,0,3] Output: 3
Constraints:
- The number of nodes in the tree is in the range
[2, 5000]. 0 <= Node.val <= 105
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int maxAncestorDiff(TreeNode root) {
int maxDiff = 0;
Queue < NodeValuePair> queue = new LinkedList<>();
queue.add(new NodeValuePair(root, root.val, root.val));
while (!queue.isEmpty()) {
NodeValuePair removed = queue.remove();
TreeNode node = removed.node;
Integer minNodeValue = removed.minNodeValue;
Integer maxNodeValue = removed.maxNodeValue;
maxDiff = Math.max(maxDiff, Math.max(Math.abs(node.val - minNodeValue), Math.abs(node.val - maxNodeValue)));
Integer updatedMinNodeValue = Math.min(node.val, minNodeValue);
Integer updatedMaxNodeValue = Math.max(node.val, maxNodeValue);
if (node.left != null) {
queue.add(new NodeValuePair(node.left, updatedMinNodeValue, updatedMaxNodeValue));
}
if (node.right != null) {
queue.add(new NodeValuePair(node.right, updatedMinNodeValue, updatedMaxNodeValue));
}
}
return maxDiff;
}
private static class NodeValuePair {
private TreeNode node;
private Integer minNodeValue;
private Integer maxNodeValue;
public NodeValuePair(TreeNode node, Integer minNodeValue, Integer maxNodeValue) {
this.node = node;
this.minNodeValue = minNodeValue;
this.maxNodeValue = maxNodeValue;
}
}
}
Input
root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output
7
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const maxAncestorDiff = function(root) {
const arr = []
dfs(root, [], arr)
let res = Number.MIN_VALUE
for(let i = 0; i < arr.length; i++) {
let el = arr[i]
let max = Number.MIN_VALUE
let min = Number.MAX_VALUE
for(let j = 0; j < el.length; j++) {
if(el[j] < min> min = el[j]
if(el[j] > max) max = el[j]
}
if(Math.abs(max - min) > res) res = Math.abs(max - min)
}
return res
};
function dfs(node, arr, res) {
if(node == null) return
arr.push(node.val)
if(node.left === null && node.right === null) {
res.push(arr.slice(0))
return
}
dfs(node.left, arr.slice(0), res)
dfs(node.right, arr.slice(0), res)
}
Input
root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output
7
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def maxAncestorDiff(self, root: TreeNode) -> int:
self.res = 0
def dfs(node):
mx = mn = node.val
if node.left:
lMn, lMx = dfs(node.left)
mx = max(mx, lMx)
mn = min(mn, lMn)
self.res = max(self.res, abs(lMn - node.val), abs(lMx - node.val))
if node.right:
rMn, rMx = dfs(node.right)
mx = max(mx, rMx)
mn = min(mn, rMn)
self.res = max(self.res, abs(rMn - node.val), abs(rMx - node.val))
return mn, mx
dfs(root)
return self.res
Input
root = [1,null,2,null,0,3]
Output
3
#4 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _1026_MaximumDifferenceBetweenNodeAndAncestor
{
public int MaxAncestorDiff(TreeNode root)
{
return MaxAncestorDiff(root, root.val, root.val);
}
private int MaxAncestorDiff(TreeNode node, int min, int max)
{
if (node == null) return max - min;
if (node.val < min)
min = node.val;
else if (node.val > max)
max = node.val;
return Math.Max(MaxAncestorDiff(node.left, min, max), MaxAncestorDiff(node.right, min, max));
}
}
}
Input
root = [1,null,2,null,0,3]
Output
3