나는 Bfs를 못한다. 따로 bfs의 문제의 풀이 흐름을 이해하기 위해 bfs101을 하려고 한다.
나중에 안 사실인데 title 순으로 정렬하다 보니 tree 문제만 풀었다 ㅎㅎㅎ...
아름다운 코드들은 해당 문제 discuss 를 확인하시면 멋진 아이디어들이 다양하게 있으니 한번 찾아보자.
100. Same Tree
트리노드 두 개가 주어지고 두 개의 노드가 동일한 노드인지 를 체크하는 문제이다. 바로 루트 노드부터 bfs로 트리를 계층으로 타고 내려 갈 생각 하면서 비교를 할 생각을 하였다.
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(p == null || q == null) return false;
Deque<TreeNode> q1 = new ArrayDeque<>();
Deque<TreeNode> q2 = new ArrayDeque<>();
q1.add(p);
q2.add(q);
while(!q1.isEmpty() && !q2.isEmpty()){
TreeNode curOne = q1.poll();
TreeNode curTwo = q2.poll();
if(curOne ==null && curTwo != null) return false;
if(curOne != null && curTwo == null) return false;
if(curOne.val != curTwo.val) return false;
//left null check
if(curOne.left != null){
q1.add(curOne.left);
if(curTwo.left == null){return false;}
}
if(curTwo.left != null){
q2.add(curTwo.left);
if(curOne.left == null){return false;}
}
//right null check
if(curOne.right != null){
q1.add(curOne.right);
if(curTwo.right == null){return false;}
}
if(curTwo.right != null){
q2.add(curTwo.right);
if(curOne.right == null){return false;}
}
}
return true;
}
}릿코드 답게 예상하지 못한 예외 케이스가 존재한다 ㅎㅎ, 풀이 의 과정은 2개의 2 덱을 선언해서 각각의 트리를 bfs로 순환해서 타 줄 것이다. 대신 그 중간에 null 값은 들어가지 못하게 예외처리를 분명하게 해주어야 한다. 이렇게 해도 통과되는 이유는 양쪽의 노드가 동일한 노드인지를 확인해주는 것이기 때문에 null 값은 체크 안 하고 넘겨주면 된다. if 처리가 복잡해서 그렇지 시간적 여유를 가지고 천천히 작성하면 한 번에 통과될 수준의 문제이다.
이 코드가 이해가 안 된다면 뒤에 문제들 은 전부 손볼 수가 없다. 확실히 이해하고 넘어가자.
참고로 모든 트리 순회 문제는 dfs 풀이가 2000배 섹시하다. 내가 좋아하는 풀이법이니 첨부하자.
Dfs풀이
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
return isSameNode(p, q);
}
public boolean isSameNode(TreeNode p, TreeNode q){
if(p == null && q == null){
return true;
}else if(p == null || q == null){
return false;
}
if((p.val != q.val) || !isSameNode(p.left, q.left) || !isSameNode(p.right, q.right)){
return false;
}
return true;
}
}101. Symmetric Tree
음? ㅋㅋㅋ 위의 문제가 정확히 일치하는 트리노드를 찾는 것이라면 이건 대칭되는 트리 노드를 찾는 것이다. 즉 위의 코드에서 q에 들어가 탐색할 대상이 deque 1 은 기존과 동일하게 그렇지만 deque 2는 기존과 반대로 넣어주면 해결되는 문제이다. 이해가 안 된다면 4층 레이어도 그려 본다면 느낌이 올 것이다. 풀이를 보자 위의 풀이와 다를게 크게 없다.
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root.left == null && root.right == null) return true;
if(root.left == null || root.right == null) return false;
Deque<TreeNode> left = new ArrayDeque<>();
Deque<TreeNode> right = new ArrayDeque<>();
left.add(root.left);
right.add(root.right);
while(!left.isEmpty() && !right.isEmpty()){
TreeNode leftPoll = left.poll();
TreeNode rightPoll = right.poll();
if(leftPoll.val != rightPoll.val) return false;
//left check
if(leftPoll.left != null && rightPoll.right == null) return false;
if(leftPoll.left == null && rightPoll.right != null) return false;
if(leftPoll.left != null && rightPoll.right != null){
left.add(leftPoll.left);
right.add(rightPoll.right);
}
//right check
if(leftPoll.right != null && rightPoll.left == null) return false;
if(leftPoll.right == null && rightPoll.left != null) return false;
if(leftPoll.right != null && rightPoll.left != null){
left.add(leftPoll.right);
right.add(rightPoll.left);
}
}
if(left.size() > 0 || right.size() > 0) return false;
return true;
}
}처음 주어지는 노드의 null 체크를 진행한 후 bfs를 진행한다. 비교대상이 될 왼쪽의 왼쪽 자식, 오른쪽의 오른쪽 자식을 null 및 추가해주는 과정을 진행하고 반대로 왼쪽의 오른쪽 자식, 오른쪽의 왼쪽 자식을 비교해주면 된다.
while의 과정을 각 덱의 사이즈 0 전까지만 실행한 이후에도 덱 안에 노드가 남아있다면 그건 비대칭 트리이다 한쪽이 더 길다는 소리이니깐..
Dfs풀이
public boolean isSymmetric(TreeNode root) {
return root==null || isSymmetricHelp(root.left, root.right);
}
private boolean isSymmetricHelp(TreeNode left, TreeNode right){
if(left==null || right==null)
return left==right;
if(left.val!=right.val)
return false;
return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left);
}102. Binary Tree Level Order Traversal
오 계층별로 트리를 탐색하는 문제이다. 이 문제를 보자마자 백준의 토마토 완숙이랑 리코드 썩은 오렌지가 생각난다.
미디엄 난이도인데 위에 트리 발리데이션 체크하는 거보다 쉽게 풀었다. 각 층 별로 탐색한 후 list에 담아 준다고 생각하면 된다. 이건 말보다 코드를 보는 것이 2000 배 이해하기 쉽다.
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) return result;
Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);
while(!q.isEmpty()){
int n = q.size();
List<Integer> attach = new ArrayList<>();
for(int i=0;i<n;i++){
TreeNode cur = q.poll();
attach.add(cur.val);
if(cur.left != null){
q.add(cur.left);
}
if(cur.right != null){
q.add(cur.right);
}
}
result.add(attach);
}
return result;
}
}최초 정답을 배열 List를 생성하고 만약 주어지는 노드가 null이라면 그냥 비어있는 list를 반환해준다.
기본적인 틀은 위와 동일하게 현재 노드들을 담을 덱을 만들고 bfs이다
단 while 안에서는 현재 덱 안에 들어있는 사이즈만큼 돌게 된다면? 그것이 바로 현재 진행 중인 깊이이다. 따라서 이 깊이에 따라 새로운 리스트를 만들고 그 리스트를 정답에 추가해주면 되는 것이다.
Dfs풀이
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null)
return res;
levelOrderHelper(res, root, 0);
return res;
}
public void levelOrderHelper(List<List<Integer>> res, TreeNode root, int level) {
if (root == null)
return;
List<Integer> curr;
if (level >= res.size()) {
curr = new ArrayList<>();
curr.add(root.val);
res.add(curr);
} else {
curr = res.get(level);
curr.add(root.val);
//res.add(curr); // No need to add the curr into the res, because the res.get(index) method does not remove the index element
}
levelOrderHelper(res, root.left, level + 1);
levelOrderHelper(res, root.right, level + 1);
}
103. Binary Tree Zigzag Level Order Traversal
응...? 이번에는 계층 간의 출력이긴 하지만 중간에 계속 방향을 바꾸어 주어야 한다. 홀수 층 일 때는 정방향 짝수층일 때는 역방향이니 홀수 짝수 층 구분할 불리언 변수로 주고 , 컬렉션 리버스를 이용해 정답에 계속 더해주자.
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) return result;
Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);
boolean isOdd = true;
while(!q.isEmpty()){
int n = q.size();
List<Integer> attach = new ArrayList<>();
for(int i=0;i<n;i++){
TreeNode cur = q.poll();
attach.add(cur.val);
if(cur.left != null){
q.add(cur.left);
}
if(cur.right != null){
q.add(cur.right);
}
}
if(isOdd){
result.add(attach);
}else{
Collections.reverse(attach);
result.add(attach);
}
isOdd = !isOdd;
}
return result;
}
}정확하게 위위 코드와 같고 중간에 컬렉션 리버스와 odd라는 불리언을 변경해준다.
Dfs풀이
public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
dfs(root, 0, ret);
return ret;
}
private void dfs(TreeNode node, int l, List<List<Integer>> ret) {
if (node != null) {
if (l == ret.size()) {
List<Integer> level = new ArrayList<>();
ret.add(level);
}
if (l % 2 == 1) {
ret.get(l).add(0, node.val); // insert at the beginning
} else {
ret.get(l).add(node.val);
}
dfs(node.left, l+1, ret);
dfs(node.right, l+1, ret);
}
}
104. Maximum Depth of Binary Tree
노드의 최대 깊이를 찾아주는 문제이다. bfs를 돌려 q 안에 값이 없을 때 까지 돌린다면 최고 층을 손쉽게 찾을 수 있다.
class Solution {
public int maxDepth(TreeNode root) {
int result = 0;
if(root == null) return result;
Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);
while(!q.isEmpty()){
int n = q.size();
for(int i=0;i<n;i++){
TreeNode cur = q.poll();
if(cur.left != null){
q.add(cur.left);
}
if(cur.right != null){
q.add(cur.right);
}
}
result++;
}
return result;
}
}계층 별로 탐색하기 위해 사이즈만큼 폴을 진행하고 더해준다. 그러한 일련의 과정 중 깊이를 측정해 리턴해준다.
Dfs풀이
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}107. Binary Tree Level Order Traversal II
트리 레벨 순회인데 역순이다. 위에서 진행했던 트리 오더를 리벌스 해서 제출해주자.
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if(root == null) return result;
Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);
while(!q.isEmpty()){
int n = q.size();
List<Integer> attach = new ArrayList<>();
for(int i=0;i<n;i++){
TreeNode cur = q.poll();
attach.add(cur.val);
if(cur.left != null) q.add(cur.left);
if(cur.right != null) q.add(cur.right);
}
result.add(attach);
}
Collections.reverse(result);
return result;
}
}이렇게 말고도 정답을 linkedList로 생성해서 result.add(0, attach); 이런 식으로 하는 사람도 있었다. 확실히 리버스 보다 링크드 리스트 앞으로 삽입 하느것이 빠르다 속도적인 측면에서의 차이는 없었으나 제출자 들 사이에서 의 속도 차이는 많이 유의미했다.
Dfs풀이
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
levelMaker(wrapList, root, 0);
return wrapList;
}
public void levelMaker(List<List<Integer>> list, TreeNode root, int level) {
if(root == null) return;
if(level >= list.size()) {
list.add(0, new LinkedList<Integer>());
}
levelMaker(list, root.left, level+1);
levelMaker(list, root.right, level+1);
list.get(list.size()-level-1).add(root.val);
}
}
111. Minimum Depth of Binary Tree
음? 이번에는 트리 깊이의 최솟값을 구하면 된다 bfs 돌다가 처음 자식들이 null 인 경우의 깊이를 반환해주면 된다.
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int d = 1;
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while(!q.isEmpty()){
int n = q.size();
// for each level
for(int i=0;i<n;i++){
TreeNode node = q.poll();
if(node.left == null && node.right == null){
return d;
}
if(node.left != null){
q.offer(node.left);
}
if(node.right != null){
q.offer(node.right);
}
}
d++;
}
return d;
}
}
특별할 것 없는 코드이다. 위에 설명한 대로 최초 만난 자식 없는 노드는 리프임으로 현재 깊이를 반환해준다.
이 문제는 dfs 보다는 bfs 가 더 괜찮다고 생각한다. 왼쪽에는 노드 한 개가 있지만 오른쪽은 노드가 500 층까지 있다고 생각하면 bfs의 경우 왼쪽 노드 한 개를 탐 새하고 리턴 하지만, dfs의 경우 반대쪾 500 개 모두를 탐색해야 한다. 그래도 dfs 코드는 섹시하니깐 첨부한다.
Dfs풀이
public class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;
}
}112. Path Sum
이 문제는 트리 가 주어지고 타깃 값이 주어지면 현재 시작점부터 리프까지 그중에 타겟값이 존재하냐는 문제이다. 처음 - 값의 제한상을 보지 못해서 트리의 bfs를 진행함과 동시에 가중치를 넘겨주었다 이 가중치가 타깃보다 크다면 q에 추가를 하지를 않았는데 제한사항을 보니 - 값이 있기에 위의 최적화 부분을 제외해 주었다.
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
Deque<TreeNode> q = new ArrayDeque<>();
q.add(root);
while(!q.isEmpty()){
TreeNode cur = q.poll();
if(cur.val == targetSum && cur.left ==null && cur.right ==null) return true;
if(cur.left != null ){
cur.left.val += cur.val;
q.add(cur.left);
}
if(cur.right != null){
cur.right.val += cur.val;
q.add(cur.right);
}
}
return false;
}
}val와 같은 값임과 동시에 리프 여야 하는 조건이 있기에 리턴 값을 위와 같이 지정해 주었다.
Dfs풀이
public boolean hasPathSum(TreeNode root, int sum) {
// recursion method
if (root == null) return false;
if (root.left == null && root.right == null && root.val == sum) return true;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}트리라고 써진 건 다 푼 줄 알았는데 밑에 문제가 더 있다... 101 2탄을 조만간 날 잡고 진행할 생각이다..
긴 글 읽어주셔서 감사합니다.
'PS > LeetcCode' 카테고리의 다른 글
| 1339. Maximum Product of Splitted Binary Tree (0) | 2022.12.10 |
|---|---|
| Easy 문제 풀기 Day1(79/610) (0) | 2022.12.03 |
| 33. Search in Rotated Sorted Array (0) | 2022.07.04 |
| 34. Find First and Last Position of Element in Sorted Array (0) | 2022.07.03 |
| 53. Maximum Subarray (0) | 2022.06.29 |