LeetCode 226번 - Invert Binary Tree

문제

주어진 이진트리를 반대로 뒤집는 문제이다.

---

살펴보기

재귀호출을 이용한 방법과, 큐를 이용한 방법이 있었다.

 

1. 재귀호출을 이용한 방법

서브트리로 내려간다.

내려가면서 임시 노드를 만들어 오른쪽 자식 노드를 저장하고, 왼쪽 자식 노드와 스왑한다.

이 때, 해당 노드만 스왑되는게 아니라 노드와 연결된 서브 트리까지 스왑된다!

 

스왑이 끝나면 다음 서브트리로 내려가서 반복한다.

 

2. 큐와 반복문을 이용한 방법

먼저 큐에 루트 노드를 넣는다.

 

반복문을 통해 큐에서 노드를 하나씩 빼면서, 즉 노드에 방문하면서 왼쪽 자식 노드와 오른쪽 자식 노드를 스왑한다.

스왑이 끝나면 다시 큐에 노드를 넣어 연결하는 방법이다. 

 

큐에서 노드를 꺼낼 때마다 한 레벨씩 아래로 이동하게 된다.

더 이상 내려갈 레벨이 없으면, 반복문이 종료된다.

 

큐에 노드를 다시 넣기 전 노드가 null인지 확인한 후 넣어야 한다..

---

풀어보기

재귀호출을 이용한 방법

if(root == null) return null;

TreeNode temp = root.right;

root.right = root.left;
root.left = temp;

invertTree(root.left);
invertTree(root.right);

return root;

 

큐를 이용한 방법

if(root == null) return null;

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

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

    TreeNode temp = node.right;
    node.right = node.left;
    node.left = temp;

    if(node.left != null) queue.offer(node.left);
    if(node.right != null) queue.offer(node.right);
}

return root;