Find maximum value |a-b| where a is an ancestor of b in a binary tree.
Input: root=[8,3,10,1,6,null,14,null,null,4,7,13] → Output: 7
Input: root=[1,null,2,null,0,3] → Output: 3
DFS passing min and max of current path. At leaf, compute |max - min|.
- DFS with current min and max along the path
- At each node: update min and max
- At null: return max - min (this is max |ancestor - node| for this path)
- Return max of left and right results
public int maxAncestorDiff(TreeNode root) {
return dfs(root, root.val, root.val);
}
private int dfs(TreeNode node, int min, int max) {
if (node == null) return max - min;
min = Math.min(min, node.val);
max = Math.max(max, node.val);
return Math.max(dfs(node.left, min, max), dfs(node.right, min, max));
}
- Time Complexity: O(n)
- Space Complexity: O(h)