144. Binary Tree Preorder Traversal
비교적 쉬운 문제이다. 트리노드 의 트리 형태의 자료구조 가 주어지면 이걸 리스트에 담아 리턴하면 된다.
순회의 방법은 전위순회 중위순회 후위순회가 있고 이 문제에서 요구하는 바는 전위순회 이다.
예전 easy 101 할때 풀었던 문제인데 그당시 에는 bfs 를 이용해 계층 별 탐색을 했으니 이번에는 재귀로 풀어보자.
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
helper(root);
return list;
}
public void helper(TreeNode root){
if(root == null) return;
list.add(root.val);
helper(root.left);
helper(root.right);
}
}별다를 바 없는 코드이다 현재 들어온 루트 를 기점으로 다음재귀 로 넘어갈때 마다 list 에 담아준다.
list.add 의 위치가 한칸 아래 내려오면 중위순회이고 맨아래 들어가면 후위순회가 된다.
Account Login - 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
100. Same Tree
위의 문제와 다를 바 없다 동일한 순회방법을 정해 태우면서 같은 값이 나오지 않는다면 false 를 바로바로 리턴해주면 된다.
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
return helper(p,q);
}
public boolean helper(TreeNode p,TreeNode q){
if(p == null || q == null)
return p==q;
if(p.val != q.val) return false;
return helper(p.left,q.left) && helper(p.right,q.right);
}
}좌우 노드를 이용해서 돌렸다. if 부분 의 return 값 이 의아할텐데 하나가 null 이고 하나가 null 이 아닌경우 에 대해 해결 해주기 위해 위와 같이 작성하엿다.
여기서 중점적으로 봐야 할 부분은 여기다 null == null 은 트루가 나온다(Objects.equals(null,null)도 트루이다.)
null 이란 특정 원시타입 혹은 객체 타입이 아닌 그냥 변수이다.
이 null 의 메모리 어드레스가 0 이라고들 말하는데 메모리 한칸을 쓰고 있는거 아니겠는가 그래서 null 값이 나오면 저 하나의 포인트 로 가기 때문에 true 값이 나온다고 이해된다.
직접 확인 해보기가 어려워서 스택오버 플로 말을 믿자..(C 나 C++ 은 0을 포인팅 한다고 한다.) 위의 이유에서 null == null 이 성립한다.
1443. Minimum Time to Collect All Apples in a Tree
생각보다 시간 소모를 많이한 문제이다.(문제를 이상하게 읽어서...) 어쩃든 보면 0 에서 시작해서 모든 사과를 수거해서 0 으로 돌아오면 된다.
사과를 가지고 올 최선의 길은 ? 항상 동일하다 같던 방향 그대로 돌아오면 된다. 단 여기서 1번 노드 는 4,5 를 1번 분기를 기준으로 다녀오면 된다.
분기를 나누는 재귀가 마구마구 떠오른다.
솔루션 의 다른 풀이 확인을 하다보니 좋은 그림이 있어 첨부한다.
가장 아래에서 부터 올라가면 된다. 사과 를 가지고 위 분기로 올라갈떄는 2를 더한다 왜 ? 갔다 와야하니깐
코드를 보자.
class Solution {
private List<List<Integer>> graph = new ArrayList<>();
private void init(int n,int[][] edges){
for (int i = 0; i < n; i++) {
graph.add(new ArrayList());
}
for (int i = 0; i < edges.length; i++) {
int from = edges[i][0],to = edges[i][1];
graph.get(from).add(to);
graph.get(to).add(from);
}
}
public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
init(n,edges);
boolean[] visit = new boolean[n];
return helper(0, hasApple, visit);
}
public int helper(int cur,List<Boolean> hasApple,boolean[] visit){
visit[cur] = true;
int move = 0;
for(int next : graph.get(cur)){
if(visit[next]) continue;
move += helper(next,hasApple,visit);
}
if(cur != 0 && (hasApple.get(cur) || move > 0)) move +=2;
return move;
}
}init 을 이용해 그래프 를 그려 주었다 예전 다익스트라 알고리즘 에서 할떄 이런 방법 으로 그래프 그렸던 기억이 있어 위와 같이 그래프를 만들었고. 중복 방문을 처리하기 위해 visit 배열을 하나 생성 했다. 다른 부분은 이상하지 않으나 저기 += 2 해주는 부분을 보자.
0 이 아니라면 왜 ? 0부터 시작하니깐 사과를 집은 시점부터 이동 거리가 0 이상이라면 계속 더해주면서 가야한다
그길은 거쳐야 하니깐 계속 2 씩 증가시켜주면서 다음으로 넘어가 준다.
'PS > LeetcCode' 카테고리의 다른 글
| LeetCode Daily 문제풀기 (0) | 2023.01.06 |
|---|---|
| LeetCode Daily 문제풀기 (0) | 2023.01.05 |
| 1월4일 문제 풀기 (2) | 2023.01.04 |
| Easy 문제 풀기 Day2(83/618) (0) | 2023.01.03 |
| Binary Tree Maximum Path Sum (0) | 2022.12.11 |
