前言
Weekly Contest 132 的 节点与其祖先之间的最大差值：
给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val – B.val|，且 A 是 B 的祖先。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
示例：
输入：[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 到 5000 之间。
每个节点的值介于 0 到 100000 之间。
解题思路
本题需要将问题分解一下，首先先实现根节点与每个节点的差值的最大值的算法，然后只需要遍历每个子树即可。
实现代码
/**
* 5030. 节点与其祖先之间的最大差值
* @param root
* @return
*/
public int maxAncestorDiff(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int max=0;
while(!queue.isEmpty()){// 层序遍历
TreeNode node=queue.poll();
max=Math.max(max,getMaxDiffByRoot(node));
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
return max;
}
/**
* 获取某个根节点下所有节点与根节点的差值的最大值
* 这里选择使用层序遍历
* @param root
* @return
*/
private int getMaxDiffByRoot(TreeNode root){
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 根节点的值，用于比较
int rootValue=root.val;
// 最大差值
int max=0;
while(!queue.isEmpty()){// 层序遍历每个节点
TreeNode node=queue.poll();
// 获取最大值
max=Math.max(max,Math.abs(node.val-rootValue));
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
return max;
}