1026. 节点与其祖先之间的最大差值

题目描述：

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

示例 2：

输入：root = [1,null,2,null,0,3]
输出：3

提示：

• 树中的节点数在 2 到 5000 之间。
• 0 <= Node.val <= 10⁵

---

解题分析及思路：

方法一：深度优先遍历(自顶向下)

思路：

采用深度优先遍历的方法，将某个节点的祖先节点的最大值、最小值维护下来，直到一条路径遍历完成计算最大值与最小值差值。

例如：

• 路径 8 - 3 - 1，最大值、最小值为 8，1，所以差值为 7
• 路径 8 - 3 - 6 - 4，最大值、最小值为 8，3，所以差值为 5
• …

以此类推，推算出每条路径的差值进行比较，最大的结果即为最终结果

func maxAncestorDiff(root *TreeNode) int {
	var dfs func(root *TreeNode, min, max int) int
	dfs = func(root *TreeNode, min, max int) int {
		if root == nil {
			return max - min
		}
		min = minFunc(min, root.Val)
		max = maxFunc(max, root.Val)
		return maxFunc(dfs(root.Left, min, max), dfs(root.Right, min, max))
	}
	return dfs(root, root.Val, root.Val)
}

func minFunc(value1, value2 int) int {
	if value2 < value1 {
		return value2
	}
	return value1
}

func maxFunc(value1, value2 int) int {
	if value2 > value1 {
		return value2
	}
	return value1
}

方法二：深度优先遍历(自底向上)

思路：

采用深度优先遍历的方法，拿到某个节点下的所有子节点的最大值、最小值，并且与当前值进行比较

例如：

• 路径 8 - 3 - 1，在节点8，其所有子节点的最大值、最小值为 7，1，所以差值为 8 - 1 = 7
• 路径 8 - 3 - 6 - 4，在节点8，其所有子节点的最大值、最小值为 6，3，所以差值为 8 - 3 = 5
• …

以此类推，推算出每条路径的差值进行比较，最大的结果即为最终结果

func maxAncestorDiff1(root *TreeNode) (result int) {
	var dfs func(root *TreeNode) (min, max int)
	dfs = func(root *TreeNode) (int, int) {
		if root == nil {
			return math.MaxInt, math.MinInt
		}
		max, min := root.Val, root.Val
		lMin, lMax := dfs(root.Left)
		rMin, rMax := dfs(root.Right)
		max = maxFunc(maxFunc(max, lMax), rMax)
		min = minFunc(minFunc(min, lMin), rMin)
		result = maxFunc(result, maxFunc(root.Val-min, max-root.Val))
		return min, max
	}
	dfs(root)
	return result
}

func minFunc(value1, value2 int) int {
	if value2 < value1 {
		return value2
	}
	return value1
}

func maxFunc(value1, value2 int) int {
	if value2 > value1 {
		return value2
	}
	return value1
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(N)

执行结果：

• 执行耗时:3 ms,击败了48.86% 的Go用户
• 内存消耗:4.1 MB,击败了15.91% 的Go用户