1026. Maximum Difference Between Node and Ancestor #

Problem #

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:

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

Problem Summary #

Given the root node root of a binary tree, find the maximum value V that exists between different nodes A and B, where V = |A.val - B.val|, and A is an ancestor of B. (If any child of A is B, or any child of A is an ancestor of B, then we consider A to be an ancestor of B.)

Note:

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

Solution Approach #

• Given a tree, find the maximum difference between an ancestor and a child.
• DFS is sufficient. The maximum value among each node and all its children comes from 3 values: the node itself, the maximum value from recursively traversing the left subtree, and the maximum value from recursively traversing the right subtree; the minimum value among each node and all its children comes from 3 values: the node itself, the minimum value from recursively traversing the left subtree, and the minimum value from recursively traversing the right subtree. Compute the maximum difference between each node itself and all its child nodes in turn, and dynamically maintain the maximum difference during the DFS process.

Code #

func maxAncestorDiff(root *TreeNode) int {
	res := 0
	dfsAncestorDiff(root, &res)
	return res
}

func dfsAncestorDiff(root *TreeNode, res *int) (int, int) {
	if root == nil {
		return -1, -1
	}
	leftMax, leftMin := dfsAncestorDiff(root.Left, res)
	if leftMax == -1 && leftMin == -1 {
		leftMax = root.Val
		leftMin = root.Val
	}
	rightMax, rightMin := dfsAncestorDiff(root.Right, res)
	if rightMax == -1 && rightMin == -1 {
		rightMax = root.Val
		rightMin = root.Val
	}
	*res = max(*res, max(abs(root.Val-min(leftMin, rightMin)), abs(root.Val-max(leftMax, rightMax))))
	return max(leftMax, max(rightMax, root.Val)), min(leftMin, min(rightMin, root.Val))
}