题目描述
- 给定一棵二叉树，找到最大的“节点与其祖先节点的差值的绝对值”
示例
输入：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
}
