5030-ノードとその祖先との最大差
前言
Weekly Contest 132のノードとその祖先との最大差:
与えられた二叉木のルートノード
(もし
例:
ヒント:ツリー内のノード数は2～5000です. 各ノードの値は0～100000です.
問題を解く構想.
この問題を分解するには、まずルートノードと各ノードの差の最大値のアルゴリズムを実現し、次に各サブツリーを巡回するだけでよい.
インプリメンテーションコード
Weekly Contest 132のノードとその祖先との最大差:
与えられた二叉木のルートノード
rootは、異なるノードAとBの間に存在する最大値VのうちV = |A.val - B.val|であり、かつAはBの祖先である.(もし
Aいずれかのサブノードの1つが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 。ヒント:
問題を解く構想.
この問題を分解するには、まずルートノードと各ノードの差の最大値のアルゴリズムを実現し、次に各サブツリーを巡回するだけでよい.
インプリメンテーションコード
/**
* 5030.
* @param root
* @return
*/
public int maxAncestorDiff(TreeNode root) {
Queue 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 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;
}