题目：
给定二叉树的根节点 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 得出。
示例2：
输入：root = [1,null,2,null,0,3]
输出：3
提示：
- 树中的节点数在 2 到 5000 之间。
- 0 <= Node.val <= 105
代码实现：
class Solution {
private:
// 辅助函数 dfs(node, int, int) 计算节点 node 与其祖先链中的最大差值并返回
// 节点与其祖先之间的最大差值一定来自于 节点值 与 祖先之中的最大值或最小值 之间的差值
int dfs(TreeNode* node, int a, int b){
if(!node) return 0; // 节点不存在则返回-1
// 计算当前节点与祖先链中差值
int diff = max(abs(node->val - a), abs(node->val - b));
// 更新 祖先链中 最大值和最小值
a = min(a, node->val);
b = max(b, node->val);
// 递归 更新 左右子树 中的最大差值
diff = max(diff, dfs(node->left, a, b));
diff = max(diff, dfs(node->right, a, b));
return diff;
}
public:
int maxAncestorDiff(TreeNode* root, int maxVal = 0, int minVal = 0) {
return dfs(root, root->val, root->val);
}
};
另一种写法：
class Solution {
private:
// 辅助函数 dfs(node, int, int) 计算节点 node 与其祖先链中的最大差值并返回
// 节点与其祖先之间的最大差值一定来自于 节点值 与 祖先之中的最大值或最小值 之间的差值
// int dfs(TreeNode* node, int minVal, int maxVal){
// if(!node) return 0; // 节点不存在则返回-1
// // 计算当前节点与祖先链中差值
// int diff = max(abs(node->val - minVal), abs(node->val - maxVal));
// // 更新 祖先链中 最大值和最小值
// minVal = min(minVal, node->val);
// maxVal = max(maxVal, node->val);
// // 递归进 更新 左右子树 中的最大差值
// diff = max(diff, dfs(node->left, minVal, maxVal));
// diff = max(diff, dfs(node->right, minVal, maxVal));
// return diff;
// }
public:
int maxAncestorDiff(TreeNode* root, int maxVal = 0, int minVal = 0) {
// 使用 function 包装器
function<int(TreeNode*,int, int)> dfs = [&](TreeNode* node, int a, int b){
if(!node) return -1;
int diff = max(abs(node->val - a), abs(node->val - b));
a = min(a, node->val);
b = max(b, node->val);
diff = max({diff, dfs(node->left, a, b), dfs(node->right, a, b)});
return diff;
};
return dfs(root, root->val, root->val);
}
};