4-18每日

1026. 节点与其祖先之间的最大差值

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例 1：

输入：root = [8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

题解

var maxAncestorDiff = function(root) {
    let result = { 
        V: 0 
    };  // 记录最大差值
    dfs(root, result);
    return result.V;
};

function dfs(root, result) {
    if (!root) {
        return { max: -Infinity, min: Infinity };
    }
    
    let { max: maxLeft, min: minLeft } = dfs(root.left, result);  // 左子节点的最大值和最小值
    let { max: maxRight, min: minRight } = dfs(root.right, result);  // 右子节点的最大值和最小值
    
    // 计算当前节点子树中的最大值和最小值
    let maxVal = Math.max(root.val, maxLeft, maxRight);
    let minVal = Math.min(root.val, minLeft, minRight);
    
    // 更新最大值
    if (root.left) {
        let diff = Math.abs(root.val - minLeft);
        if (diff > result.V) {
            result.V = diff;
        }
        diff = Math.abs(root.val - maxLeft);
        if (diff > result.V) {
            result.V = diff;
        }
    }
    if (root.right) {
        let diff = Math.abs(root.val - minRight);
        if (diff > result.V) {
            result.V = diff;
        }
        diff = Math.abs(root.val - maxRight);
        if (diff > result.V) {
            result.V = diff;
        }
    }
    
    return { max: maxVal, min: minVal };
}

如果直接使用 result = 0 来初始化结果，则会导致 result 存储的是一个数字，而不是一个对象。这样在 DFS 遍历过程中，我们无法直接修改 result 的值，而需要额外声明一个变量来保存最大差值。具体来说，我们需要在递归函数的返回值中返回最大差值，然后在计算当前节点的最大差值时，将递归返回的最大差值和当前节点的差值进行比较，取两者中的较大值作为新的最大差值。