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
- 밥먹고
- 미앤아이
- 노노그램
- 하스스톤
- 발더스게이트
- 토이프로젝트
- 3d퍼즐
- 발더스모드
- javascript
- 발더스3
- 코딩테스트
- 눈알빠지겠네
- 맛집
- 게임
- 메탈퍼즐
- DIY
- 취미
- 메일우유
- 누룽지소금빵
- LeetCode
- 코테
- 바질토마토뭐시기
- 천등
- 송리단
- 알고리즘테스트
- 뜨아거
- 버즈2프로
- 잠실새내
- 서울제빵소
- 나쫌
Archives
- Today
- Total
.Zzumbong
[leetCode/JS] 872. Leaf-Similar Trees 본문
난이도 [ 😊 ] Easy
문제 설명
Consider all the leaves of a binary tree, from left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8)
.
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true
if and only if the two given trees with head nodes root1
and root2
are leaf-similar.
2개의 2진 트리가 주어진다. 각 트리마다 마지막 leaf 가 순서와 값이 같을 때 true를 넘긴다.
입출력 예
Example 1:
Input: root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
Output: true
Example 2:
Input: root1 = [1,2,3], root2 = [1,3,2]
Output: false
Constraints
- The number of nodes in each tree will be in the range
[1, 200]
. - Both of the given trees will have values in the range
[0, 200]
.
내 솔루션
- 당연히 기본적인 DFS 방식으로 풀어야한다.
- left, right가 존재하면 dfs()를 호출하고 둘다 값이 없는 마지막 Leaf 일 때, nodes에 `/${node.val}` 로 저장한다.
- /가 필요한 이유는 1,2,3 과 12,3이 같은 값이 되기 때문.
var leafSimilar = function(root1, root2) {
const getLastNode = (root) => {
let nodes = '';
const dfs = (node) => {
if(node.left) dfs(node.left)
if(node.right) dfs(node.right)
if(!node.left && !node.right) nodes += `/${node.val}`
}
dfs(root);
return nodes;
}
return getLastNode(root1) === getLastNode(root2);
};
감상평
- easy 문제일 수록 답은 하나로 귀결될 수 밖에 없나보다 다른 사람들의 솔루션도 비슷한 방식이다.
- 메모리는 조금 많이 사용했다. 왜지! 더 적은 메모리를 사용한 솔루션을 봐도 무거워보이는데..
- 하지만 빨랐죠?
'coding test > leetCode' 카테고리의 다른 글
[leetCode/JS] 1339. Maximum Product of Splitted Binary Tree (0) | 2022.12.10 |
---|---|
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor (0) | 2022.12.09 |
[leetCode/JS] 938. Range Sum of BST (0) | 2022.12.07 |
[leetCode/JS] 328. Odd Even Linked List (0) | 2022.12.06 |
[leetCode/JS] 876. Middle of the Linked List (0) | 2022.12.05 |
Comments