LeetCode 226(Invert Binary Tree, java)

0. 문제

https://leetcode.com/problems/invert-binary-tree/

Invert Binary Tree - LeetCode

 

1. 문제 설명

- 문제에서 이진트리(root)가 주어진다.

- 문제에서 주어진 이진트리(root)를 대칭한 모양으로 바꾸는 것이 문제의 핵심이다.

 

2. 문제 해설

a) 첫 번째 접근

- 이 문제는 생각보다 간단하다. 루트 노드를 제외한 모든 자식 노드의 위치를 서로 변경하면 된다.

 

- 그러나 다음 사실을 깨닫지 못하면 문제를 푸는데 어려움을 가질 수 있다. 

   → 부모 노드의 위치가 변경되어도 각 부모 노드가 갖고 있는 자식 노드는 그대로 유지된다.

 

- 트리이기 때문에 각 노드 객체가 가지고 있는 node.left 또는 node.right의 값은 그대로 유지되기 때문이다.

 

b) 두 번째 접근

- 동일한 깊이에 존재하는 자식 노드의 위치를 swap 하는 과정을 계속해서 반복한다.

- 동일한 작업을 반복해서 수행할 때에는 재귀 함수가 가장 효율적이다. 

- 그러므로 위에서 설명한 과정을 재귀 함수로 구현하면 끝이다.

 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

class Solution {
    public TreeNode invertTree(TreeNode root) {
        
        if(root == null) return root;
        
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}