LeetCode Entry
1026. Maximum Difference Between Node and Ancestor
fun maxAncestorDiff(root: TreeNode?): Int {
1026. Maximum Difference Between Node and Ancestor medium
https://t.me/leetcode_daily_unstoppable/46
fun maxAncestorDiff(root: TreeNode?): Int {
root?: return 0
fun dfs(root: TreeNode, min: Int = root.`val`, max: Int = root.`val`): Int {
val v = root.`val`
val currDiff = maxOf(Math.abs(v - min), Math.abs(v - max))
val currMin = minOf(min, v)
val currMax = maxOf(max, v)
val leftDiff = root.left?.let { dfs(it, currMin, currMax) } ?: 0
val rightDiff = root.right?.let { dfs(it, currMin, currMax) } ?: 0
return maxOf(currDiff, leftDiff, rightDiff)
}
return dfs(root)
}
Based on math we can assume, that max difference is one of the two: (curr - max so far) or (curr - min so far).
Like, for example, let our curr value be 3, and from all visited we have min 0 and max 7.
0--3---7
- we can write helper recoursive method and compute max and min so far
Space: O(logN), Time: O(N)