226. Invert Binary Tree
처음으로 트리에 대해 공부하며 리트코드 easy 문제인 Invert Binary Tree를 풀었다.
문제 설명
Given the root of a binary tree, invert the tree, and return its root.
Example 1: 
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
제출 코드
function invertTree(root) {
if (root === null) return root;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
}
코드 설명
discuss를 통해 답안을 확인하고 다시 풀어보았다.
여러 가지 방법으로 풀 수 있다. 재귀, BFS, DFS.
나는 재귀로 풀었다.
처음 트리의 시작은 이렇다.
root.left는 [2,1,3]root.right은 [7,6,9]
처음 코드를 만났을 때, inverTree 함수에 인자로 root.right 다시 말해 [7,6,9]가 들어가게 된다.
‘7’가 root가 될 테고 ‘6’은 left, ‘9’은 right이 된다.
(이런 식으로 재귀 함수가 콜스택에 쌓인다.)
다시 9는 root가 되어 root.right을 찾게 되는 데 이때의 값을 Null이다.
이후 right과 left는 Null에 걸려서 그대로 root가 9인 값을 반환하게 된다.
invertTree(root.right)이 9를 반환한 이후, invertTree(root.left)를 실행한다. 현재 코드의 root는 7이므로 root.left인 6이 들어간다.
같은 방식으로 invertTree(root.left)는 6을 반환하게 되고 서로의 위치는 바뀌게 된다.
서로의 위치가 바뀐 후 return root를 통해 다음 코드로 넘어간다.
root가 4일 때의 첫번째 invertTree(root.right)이 끝이 났다.
invertTree(root.left)로 넘어간다.
이후 위의 순서를 반복한다.
모든 재귀가 끝나게 된다면 마지막으로 left와 right의 위치를 바꾸고 함수는 종료된다.
소감
이번에 처음 Tree와 관련된 문제를 접하고 어떻게 접근해야 하는지 감이 잡히지 않았다.
30분 정도 생각해 보고 나만의 방식으로 풀어보려 했지만 실패!
유튜브를 통해 Tree가 무엇인지 기초부터 차근차근 영상을 보면서 공부했다.
여러 가지 트리 구조와 트리 순회에 대해 알게 되었다.
- pre-order (전위 순회)
- in-order (중위 순회)
- post-order (후위 순회)
- level-order (아직 무엇인지 모른다.)
아직 누군가를 완벽하게 이해시킬 정도로 깊게 공부하지는 못했다.
하지만, 이번 문제를 통해서 부족했던 재귀에 대해서 공부할 수 있는 시간이 되었다.
단번에 이해하지 못해서 애를 먹었지만, 좋은 동료 덕분에 확실하게 이해하고 넘어갈 수 있었다. 그림으로 그려가면서 설명해줬는데 이후, 문제를 다시 한번 풀어보고 그림도 그려서 이렇게 블로그에 정리하게 되었다.
다음 번에는 DFS, BFS를 사용해서 풀어보려 한다.
참고한 유튜브: 코드 없는 프로그래밍
- Invert Binary Tree
