beepbeep

문제 주어진 이진트리를 반대로 뒤집는 문제이다. 살펴보기 재귀호출을 이용한 방법과, 큐를 이용한 방법이 있었다. 1. 재귀호출을 이용한 방법 서브트리로 내려간다. 내려가면서 임시 노드를 만들어 오른쪽 자식 노드를 저장하고, 왼쪽 자식 노드와 스왑한다. 이 때, 해당 노드만 스왑되는게 아니라 노드와 연결된 서브 트리까지 스왑된다! 스왑이 끝나면 다음 서브트리로 내려가서 반복한다. 2. 큐와 반복문을 이용한 방법 먼저 큐에 루트 노드를 넣는다. 반복문을 통해 큐에서 노드를 하나씩 빼면서, 즉 노드에 방문하면서 왼쪽 자식 노드와 오른쪽 자식 노드를 스왑한다. 스왑이 끝나면 다시 큐에 노드를 넣어 연결하는 방법이다. 큐에서 노드를 꺼낼 때마다 한 레벨씩 아래로 이동하게 된다. 더 이상 내려갈 레벨이 없으면, 반..

문제 주어진 이진 트리를 후위 순회하는 문제이다. 살펴보기 저번에 본 144번 문제와 마찬가지로 이진 트리를 막 배웠을 때 기본 개념을 복습하기 좋은 문제같다! 후위 순회는 1. 왼쪽 하위 트리를 먼저 순회하고 2. 오른쪽 하위 트리를 순회한 다음 3. 마지막으로 현재 노드를 방문하는 방식의 순회이다. 144번 문제와 비슷한 방식으로 풀되, 현재 노드의 값을 리스트에 저장하는 시점을 하위 트리 순회가 끝난 후로 미루었다. 풀어보기 public List postorderTraversal(TreeNode root) { List list = new ArrayList(); if(root!=null){ postorderTraversal(list, root); } return list; } public void p..

문제 주어진 이진 트리를 전위 순회하면서 노드 값을 리스트에 저장해 반환하는 문제이다. 살펴보기 전위 순회를 막 배운 시점에서 개념을 복습하기 좋은 문제같다! 전위 순회는 1. 현재 노드를 먼저 방문하고 2. 그 다음 왼쪽 자식 노드를 순회한 후 3. 마지막으로 오른쪽 자식 노드를 순회하는 방식이다. 풀어보기 노드값을 저장할 리스트를 선언한 후, 반환값이 void인 preorederTraversal 메서드를 호출해 리스트와 루트를 전달한다. 현재 노드가 null이면 return문을 통해 재귀 함수의 수행을 멈춘다. null이 아닌 경우 리스트에 현재 노드의 값을 추가한 후, 왼쪽 자식 노드가 있으면 preorederTraversal 메서드를 다시 호출해 리스트와 왼쪽 자식 노드를 전달해 순회한다. 왼쪽 ..

문제 소개 이진 트리와 int형 변수 targetSum이 주어진다. 루트 노드부터 리프 노드(자식 노드가 없는 노드)까지 키 값을 누적하면서 내려간다고 할 때, 누적한 값이 targetSum과 같아지는 경로가 있는지 확인해야 한다. 살펴보기 checkPathSum(TreeNode root, int targetSum) 메서드를 호출해 루트 노드부터 리프 노드가 나올 때까지 targetSum을 전달하면서 이동했다. 먼저 targetSum에서 현재 노드의 키 값을 차감한 후, 현재 노드가 리프 노드인지 확인했다. 만약 현재 노드가 리프 노드가 아닌 경우, 왼쪽 자식 노드와 오른쪽 자식 노드가 있는지 확인했다. 해당 노드가 있는 경우, checkPathSum()를 다시 호출해 다음 자식 노드와 targetSum..