1026.maximum-difference-betwwen-node-and-ancestor.md

1026. Maximum Difference Between Node and Ancestor

Test Cases

Normal Cases

Input: 
        10
       /  \
      1   15
     / \    \
    3   18  7
Output: 9

Edge / Corner Cases

• Single node

Input: 1        
Output: 1

DFS

To find the maximum difference between ancestor and node, we keep track of the maximum and minimum value of the path from the root to the current node. We can use DFS to traverse the tree and update the result with the maximum difference between the current node and the maximum and minimum value of the path from the root to the current node.

private var result = 0

fun maxAncestorDiff(root: TreeNode?): Int {
    if (root == null) return 0
    dfs(root, root.`val`, root.`val`)
    return result
}

private fun dfs(root: TreeNode?, min: Int, max: Int) {
    if (root == null) return

    result = maxOf(result, abs(root.`val` - min))
    result = maxOf(result, abs(root.`val` - max))

    val newMin = minOf(min, root.`val`)
    val newMax = maxOf(max, root.`val`)
    dfs(root.left, newMin, newMax)
    dfs(root.right, newMin, newMax)
}

• Time Complexity: O(n).
• Space Complexity: O(n).