LeetCode 101(Symmetric Tree, java)

0. 문제

https://leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

 

1. 문제 설명

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

- 해당 이진트리의 모든 노드가 가진 값을 탐색 및 비교하여 대칭하는지를 판단하는 것이 문제의 핵심이다.

 

2. 문제 해설

a) 첫 번째 접근

- 최초에 루트 노드가 가진 좌/우측 자식은 1개씩이므로, 이 둘의 value를 비교하면 대칭 판단은 쉽다. (= 깊이 1)

- 그러므로 좌/우측 둘 중 하나가 존재하지 않거나 value가 동일하지 않다면 대칭하지 않으므로 false를 반환한다.

 

b) 두 번째 접근

- 깊이가 2일 때부터 각 부모 노드는 최대 2개의 자식 노드를 가질 수 있다.

- 즉, 최대 4개의 자식 노드를 판단해야 한다.

 

- 최대 4개의 자식 노드를 판단하는 경우, 부모 노드 A의 좌측 자식과 부모 노드 B의 우측 자식을 비교한다.

- 또는 부모 노드 A의 우측 자식과 부모 노드 B의 좌측 자식을 비교한다. 

- 이렇게 엇갈리게 비교하는 이유는 대칭을 판단하기 위해서다.

 

c) 세 번째 접근

 - 정리하자면, 깊이가 2 이상인 경우에는 다음과 같은 판단 조건을 가지게 된다.

    → 각 부모 노드가 대칭된 위치에 자식 노드를 가지고 있는가

    → 각 부모 노드가 가진 대칭된 위치의 자식 노드가 동일한 value를 가지고 있는가

 

d) 네 번째 접근 

- 동일한 비교 과정을 트리를 탐색하는 동안 반복한다.

- 동일한 작업을 반복해서 진행하는 경우, 재귀 함수를 사용하는 것이 가장 효율적이다. 

 

- 재귀의 탈출 조건은 더 이상 비교할 노드가 없는 단말 노드에 도착한 경우다. 

- 재귀 탈출 조건까지 탐색을 하는 동안, 모든 조건을 통과했다면 이는 대칭하므로 true를 반환한다.

 

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

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

 

3. 정답 코드

class Solution {
    public boolean isSymmetric(TreeNode root) {
        
        if(root == null) return false;
        
        return checkSymmetric(root.left, root.right);
    }
    
    public boolean checkSymmetric(TreeNode leftParent, TreeNode rightParent) {
        
        if(leftParent == null && rightParent == null) return true;
        if(leftParent == null || rightParent == null) return false;
        if(leftParent.val != rightParent.val) return false;
        
        return checkSymmetric(leftParent.left, rightParent.right) && 
                 checkSymmetric(leftParent.right, rightParent.left);
    }