beepbeep

LeetCode 226번 - Invert Binary Tree 본문

코딩테스트 연습/트리

LeetCode 226번 - Invert Binary Tree

삑삑도요 2023. 2. 11. 15:48

문제

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


살펴보기

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

 

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;