Invert Binary Tree

---

💬 문제

[문제 링크]

이진 트리의 시작점 노드 root
주어진 트리를 좌우반전한 형태로 만들어 반환

✍️ 나의 풀이

/**트리노드 클래스 생략*/
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    let queue = [root];

    while (queue[0]) {
        let node = queue.shift();
        let left = node.left;
        node.left = node.right;
        node.right = left;

        if (node.left)
            queue.push(node.left);
        if (node.right)
            queue.push(node.right);
    }

    return root;
};

queue에 저장된 노드를 하나 뽑아서 왼쪽 자식과 오른쪽 자식을 서로 swap해줌
그리고 다시 왼쪽 자식과 오른쪽 자식을 queue에 저장 (null이 아닐때만)
같은 방식으로 모든 노드의 자식을 서로 교환하고 나면 좌우반전된 트리 완성

📌 결과

Accepted
Runtime 27ms (Beats 100%)
Memory 49.38MB (Beats 33.24%)

📚 러닝 포인트

아무리 리트코드 테스트가 정말 자기 맘대로라고 하지만 Beats 100%가 나온다니... 어쨌든 이번 문제는 BFS로 먼저 풀어보았다. 딱 문제랑 예시 그림을 보고 각 Depth의 노드를 싹 수정하고 그 다음으로 넘어가고 하는게 좋아보여서 BFS를 사용했는데, 결과 화면에서 다른 코드들 둘러보니 DFS가 대부분이었다. 하긴 결국 모든 노드를 방문해야하는 건 맞았다. 근데 왜 DFS가 더 선호되는 걸까?하고 조금 찾아봤더니 시간 복잡도는 비슷하지만 재귀함수 VS 반복문으로 봤을 때는 재귀함수가 조금 더 빠르기 때문이라고 한다. 그래서 나도 DFS로도 풀어봤다.

var invertTree = function(root) {
    if (root === null)
        return root;
    let left = invertTree(root.left);
    let right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

특정 노드의 자식을 기준으로 아래 depth의 노드들이 모두 swap을 마치면 왼쪽 자식과 오른쪽 자식을 swap 해주는 과정을 반복하는 방식이다. 가장 밑에서부터 반전되면서 올라온다고 생각하면 된다.