Leetcode学習ノート:#1026.Maximum Difference Between Node and Ancestor
774 ワード
Leetcode学習ノート:#1026.Maximum Difference Between Node and Ancestor
Given the root of a binary tree, find the maximum value V for which there exists 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.)
実装:
考え方:nullノードに遭遇して最大差を返すまでツリーの最大値と最小値を保存します.
Given the root of a binary tree, find the maximum value V for which there exists 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.)
実装:
public int maxAncestorDiff(TreeNode root) {
return dfs(root, root.val, root.val);
}
public int dfs(TreeNode root, int mn, int mx) {
if (root == null) return mx - mn;
mx = Math.max(mx, root.val);
mn = Math.min(mn, root.val);
return Math.max(dfs(root.left, mn, mx), dfs(root.right, mn, mx));
}
考え方:nullノードに遭遇して最大差を返すまでツリーの最大値と最小値を保存します.