Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 잠실새내
- 메탈퍼즐
- 뜨아거
- DIY
- 발더스게이트
- 노노그램
- 미앤아이
- 밥먹고
- 발더스모드
- 송리단
- javascript
- 알고리즘테스트
- 발더스3
- 코딩테스트
- 바질토마토뭐시기
- 하스스톤
- 버즈2프로
- 눈알빠지겠네
- 3d퍼즐
- LeetCode
- 게임
- 토이프로젝트
- 코테
- 나쫌
- 메일우유
- 누룽지소금빵
- 서울제빵소
- 취미
- 맛집
- 천등
Archives
- Today
- Total
.Zzumbong
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor 본문
coding test/leetCode
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor
쭘봉 2022. 12. 9. 10:48난이도 [ 🤔 ] Medium
문제 설명
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
.
이진트리의 상위, 하위 노드의 a-b 의 최대값을 찾는 문제다.
입출력 예
Example 1:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.
Example 2:
Input: root = [1,null,2,null,0,3]
Output: 3
Constraints
The number of nodes in the tree is in the range [2, 5000]
.0 <= Node.val <= 105
내 솔루션
- 2진트리 DFS로 서치한다.
- left, right로 나눠진 트리를 서치하면서 max, min을 구한다.
- 마지막 노드일때 max - min 해서 left와 right 트리의 큰 값을 리턴한다.
var maxAncestorDiff = function(root) {
const dfs = (node, max, min) => {
if(!node) return Math.abs(max - min);
max = Math.max(max, node.val)
min = Math.min(min, node.val)
let leftMax = dfs(node.left, max, min);
let rightMax = dfs(node.right, max, min);
return Math.max(leftMax, rightMax)
}
return dfs(root, 0, Infinity);
};
감상평
- return 값을 이용하여 dfs로 풀면 쉽다.
- 요즘 이진트리 서치나 dfs 위주로 나와서 덕분에 DFS에 자신감이 많이 생겼다.
'coding test > leetCode' 카테고리의 다른 글
[leetCode/JS] 124. Binary Tree Maximum Path Sum (0) | 2022.12.11 |
---|---|
[leetCode/JS] 1339. Maximum Product of Splitted Binary Tree (0) | 2022.12.10 |
[leetCode/JS] 872. Leaf-Similar Trees (0) | 2022.12.08 |
[leetCode/JS] 938. Range Sum of BST (0) | 2022.12.07 |
[leetCode/JS] 328. Odd Even Linked List (0) | 2022.12.06 |
Comments