Given the root of a binary tree, find the maximum value V for which there exist 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.
이진트리의 루트가 주어진다. V의 최댓값을 구해라
A가 B의 조상인 경우에 V = |A.val - B.val|
A가 B의 조상이라고 말하는 경우는 아래와 같다
A의 어떠한 자식이 B와 같은 경우 거나, A의 어떠한 자식이든 B의 선조인 경우이다.
( 쉽게 말해, 이진트리에 존재하는 노드의 값들 중 노드의 값의 차가 최댓값인 것을 구해라 )
dfs를 이용해서 해답을 구해보자.
노드를 방문하며, 지금까지 구한 min, max값을 파라미터로 넘기고
현재 방문한 노드의 값이 min, max값에 해당하는지 비교하여 값을 업데이트 한 후에
min과 max의 차를 result로 저장하면 된다.
private void dfs(TreeNode node, int min, int max) {
min = Math.min(node.val, min);
max = Math.max(node.val, max);
rst = Math.max(rst, max -min);
if (node.right != null) {
dfs(node.right, min, max);
}
if (node.left != null) {
dfs (node.left, min, max);
}
}해당 메소드를 호출하는 부분을 보자.
결과 값은 전역변수로 선언하였다.
int rst = 0;
public int maxAncestorDiff(TreeNode root) {
if (root != null) {
dfs (root, root.val, root.val);
}
return rst;
}전역 변수를 사용하지 않는 경우에는 result가 되는 값을 파라미터로 넘기면 된다.
public int maxAncestorDiff(TreeNode root) {
int rst = 0;
if (root != null) {
rst = dfs (root, root.val, root.val, 0);
}
return rst;
}
private int dfs(TreeNode node, int max, int min, int rst) {
min = Math.min(node.val, min);
max = Math.max(node.val, max);
rst = Math.max(rst, max -min);
int right = rst;
if (node.right != null) {
right = dfs(node.right, max, min,rst);
}
int left = rst;
if (node.left != null) {
left = dfs (node.left, max, min, rst);
}
return Math.max(left, right);
}
문제 출처
leetcode.com/problems/maximum-difference-between-node-and-ancestor/
Maximum Difference Between Node and Ancestor - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com