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 <= 105
解题分析及思路:
方法一:深度优先遍历(自顶向下)
思路:
采用深度优先遍历的方法,将某个节点的祖先节点的最大值、最小值维护下来,直到一条路径遍历完成计算最大值与最小值差值。
例如:
- 路径 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用户