2022-12-09.md

题目

1026. Maximum Difference Between Node and Ancestor

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

思路

代码

var maxAncestorDiff = function(root) {
  let max = -1
  function dfs(node, upper, lower) {
    if (node == null) return
    max = Math.max(max, Math.abs(node.val - upper), Math.abs(node.val - lower))
    upper = Math.max(upper, node.val)
    lower = Math.min(lower, node.val)
    dfs(node.left, upper, lower)
    dfs(node.right, upper, lower)
  }
  dfs(root, root.val, root.val)
  return max
}