[LeetCode/JAVA] 226. Invert Binary Tree

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/invert-binary-tree/

Invert Binary Tree - LeetCode

문제 설명

출처 : LeetCode

이진트리가 주어지면 트리를 좌우로 반전시켜 반환합니다.

풀이 방법

기본 BFS 탐색 로직을 사용하였습니다.
1. 자식노드들이 모두 있다면 좌우 switch를 해줍니다.
2. 왼쪽만 자식 노드가 있다면 왼쪽을 null, 오른쪽에 왼쪽 노드를 저장합니다.
3. 오른쪽에만 자식 노드가 있다면 오른쪽을 null, 왼쪽에 오른쪽 노드를 저장합니다.

내 코드(JAVA)

 

public TreeNode invertTree(TreeNode root) {
    if(root == null) return null;
    Queue<TreeNode> q = new LinkedList<>();

    q.offer(root);

    while (!q.isEmpty()) {
        int size = q.size();

        for(int i=0; i<size; i++) {
            TreeNode node = q.poll();

            if(node.left != null && node.right != null) {
                q.offer(node.right);
                q.offer(node.left);

                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            } else if(node.left != null) {
                q.offer(node.left);

                node.right = node.left;
                node.left = null;
            } else if(node.right != null) {
                q.offer(node.right);

                node.left = node.right;
                node.left = null;
            }
        }
    }
    return root;
}

스터디 피드백 내용

1. 탐색 순서와 관련이 없이 반전만 시키면 되므로 안쪽 반복문은 불필요함
2. 굳이 조건문을 통해서 null을 대입하지 않아도 된다. null로 바로 switch 가능하기 때문

 

public static TreeNode invertTree(TreeNode root) {
    if(root == null) return null;

    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
        TreeNode node = q.poll();

        // 해당 node 좌우반전, 2번에 해당
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        // null이 아닌 노드들 큐에 추가
        if(node.left != null) {
            q.offer(node.left);
        }
        if(node.right != null) {
            q.offer(node.right);
        }
    }
    return root;
}

 

탐색 순서에 영향이 없는 문제에서는 굳이 안쪽 반복문을 사용해야 하는지 충분히 고려할 것

TreeNode 클래스이기 때문에 null과 switch 가능하는 점을 기억할 것