Description
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
Solutions
Solution 1: DFS
For each node, to find the maximum difference with its ancestor nodes, we only need to find the difference between the maximum and minimum values of the ancestor nodes. The maximum difference among all nodes and their ancestor nodes is the answer.
Therefore, we design a function dfs(root, mi, mx), where the current node being searched is root, the maximum value of its ancestor nodes is mx, and the minimum value is mi. The function updates the maximum difference ans.
The logic of the function dfs(root, mi, mx) is as follows:
- If root is null, return directly.
- Otherwise, we update ans = max(ans, |mi - root.val|, |mx - root.val|).
- Then update mi = min(mi, root.val), mx = max(mx, root.val), and recursively search the left and right subtrees.
In the main function, we call dfs(root, root.val, root.val), and finally return ans.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
PythonJavaC++GoTypeScriptJavaScriptC#
# 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: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode], mi: int, mx: int):
if root is None:
return
nonlocal ans
ans = max(ans, abs(mi - root.val), abs(mx - root.val))
mi = min(mi, root.val)
mx = max(mx, root.val)
dfs(root.left, mi, mx)
dfs(root.right, mi, mx)
ans = 0
dfs(root, root.val, root.val)
return ans(code-box)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int ans;
public int maxAncestorDiff(TreeNode root) {
dfs(root, root.val, root.val);
return ans;
}
private void dfs(TreeNode root, int mi, int mx) {
if (root == null) {
return;
}
int x = Math.max(Math.abs(mi - root.val), Math.abs(mx - root.val));
ans = Math.max(ans, x);
mi = Math.min(mi, root.val);
mx = Math.max(mx, root.val);
dfs(root.left, mi, mx);
dfs(root.right, mi, mx);
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxAncestorDiff(TreeNode* root) {
int ans = 0;
function<void(TreeNode*, int, int)> dfs = [&](TreeNode* root, int mi, int mx) {
if (!root) {
return;
}
ans = max({ans, abs(mi - root->val), abs(mx - root->val)});
mi = min(mi, root->val);
mx = max(mx, root->val);
dfs(root->left, mi, mx);
dfs(root->right, mi, mx);
};
dfs(root, root->val, root->val);
return ans;
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxAncestorDiff(root *TreeNode) (ans int) {
var dfs func(*TreeNode, int, int)
dfs = func(root *TreeNode, mi, mx int) {
if root == nil {
return
}
ans = max(ans, max(abs(mi-root.Val), abs(mx-root.Val)))
mi = min(mi, root.Val)
mx = max(mx, root.Val)
dfs(root.Left, mi, mx)
dfs(root.Right, mi, mx)
}
dfs(root, root.Val, root.Val)
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function maxAncestorDiff(root: TreeNode | null): number {
const dfs = (root: TreeNode | null, mi: number, mx: number): void => {
if (!root) {
return;
}
ans = Math.max(ans, Math.abs(root.val - mi), Math.abs(root.val - mx));
mi = Math.min(mi, root.val);
mx = Math.max(mx, root.val);
dfs(root.left, mi, mx);
dfs(root.right, mi, mx);
};
let ans: number = 0;
dfs(root, root.val, root.val);
return ans;
}(code-box)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxAncestorDiff = function (root) {
let ans = 0;
const dfs = (root, mi, mx) => {
if (!root) {
return;
}
ans = Math.max(ans, Math.abs(mi - root.val), Math.abs(mx - root.val));
mi = Math.min(mi, root.val);
mx = Math.max(mx, root.val);
dfs(root.left, mi, mx);
dfs(root.right, mi, mx);
};
dfs(root, root.val, root.val);
return ans;
};(code-box)
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
private int ans;
public int MaxAncestorDiff(TreeNode root) {
dfs(root, root.val, root.val);
return ans;
}
private void dfs(TreeNode root, int mi, int mx) {
if (root == null) {
return;
}
int x = Math.Max(Math.Abs(mi - root.val), Math.Abs(mx - root.val));
ans = Math.Max(ans, x);
mi = Math.Min(mi, root.val);
mx = Math.Max(mx, root.val);
dfs(root.left, mi, mx);
dfs(root.right, mi, mx);
}
}(code-box)
