资讯详情

题目描述

• 给定一棵二叉树，找到最大的“节点与其祖先节点的差值的绝对值”

示例

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释：8/ \3   10/ \    \
1   6    14/ \   /4   7 13|8 - 1| = 7

输入：root = [1,null,2,null,0,3]
输出：3
解释：1\2\0/3|0 - 3| = 3

题解

• 思路：dfs
  • 每层计算一下和当前节点的值与上面的最大值、最小值的“绝对差值”
  • 每层都要更新最大值、最小值

func maxAncestorDiff(root *TreeNode) int {v := root.Valreturn max(dfs(root.Left, v, v), dfs(root.Right, v, v))
}func dfs(p *TreeNode, minv, maxv int) int {if p == nil { return -1 }v := p.Valres := max(myabs(v - minv), myabs(v - maxv))minv, maxv = min(minv, v), max(maxv, v)return max(res, dfs(p.Left, minv, maxv), dfs(p.Right, minv, maxv))
}func myabs(x int) int {if x < 0 { x *= -1 }return x
}