[99클럽 코테 스터디] 14일차 TIL 이분탐색

 

 

오늘의 문제는 LeetCode

 

101. Symmetric Tree

 

 

문제

 

 

 

문제 설명 

 

이진트리의 root가 주어졌을 때 트리의 중심을 기준으로 좌우가 대칭인지를 확인해 맞으면 true, 틀리면 false를 반환하는 문제입니다. 

예를 들어 입력이 root = [1,2,2,3,4,4,3]라면 true를 반환하고, 입력이 root = [1,2,2,null,3,null,3]라면 false를 반환해야 합니다. 

 

 

 

문제 풀이 시간 

권장 풀이 시간은 30분이었고, 저는 36분이 걸렸습니다. 

 

 

 

문제 접근 방식

트리의 구조를 탐색하고 비교하는데 유용한 재귀함수를 통해 문제를 풀었습니다. 

문제에서 주어진 조건에 따라 트리의 좌우 대칭을 확인해야 하기 때문에 서브트리를 반복적으로 비교하는 작업을 해야 합니다. 따라서 재귀 함수를 사용해 이러한 과정을 간결하게 해결하도록 했습니다. 

두 노드가 대칭인지 확인하는 재귀 함수를 구현하기 위해 먼저 기저 조건을 설정했습니다. 여기서 기저  조건이란 무한 호출을 멈추게 하는 중단 조건을 의미합니다. 

 

 

 

문제 풀이

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        
        if(root == null) {
            return true; 
        }
        return isMirror(root.left, root.right);

    }

    public boolean isMirror(TreeNode left, TreeNode right) {
        if(left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false; 
        } else if (left.val != right.val) {
            return false; 
        } 
        return isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

 

 

재귀함수의 기저 조건 설정 알아보기 

기저 조건은 재귀 호출을 멈추는 정확한 시점을 정의해야 합니다. 안그러면 스택 오버플로우가 발생할 수 있기 때문입니다. 

• 두 노드가 null 인 경우, 대칭입니다. 
• 두 노드 중 한 노드만 null인 경우, 비대칭입니다. 
• 두 노드의 값이 다른 경우, 비대칭입니다. 

 

 

 

재귀 함수 작동 방식 자세히 알아보기 

1. 기저 조건 확인하기 

두 노드가 모두 null인 경우 대칭이므로 true를 반환하고 한 노드만 null인 경우 비대칭이기 때문에 false를 반환합니다. 

2. 노드 값 비교하기 

두 노드의 값이 다르면 비대칭이므로 false를 반환합니다. 

3. 재귀 호출 

왼쪽 노드의 왼쪽 자식과 오른쪽 노드의 오른쪽 자식을 비교하고, 왼쪽 노드의 오른쪽 자식과 오른쪽 자식노드의 왼쪽 자식을 비교해 모두 대칭인 경우에만 true를 반환합니다. 

 

이처럼 재귀적으로 트리의 모든 노드를 비교함으로써 트리가 좌우 대칭인지 아닌지를 파악할 수 있게 됩니다. 

 

 

 

 

 

 

이렇게 오늘 14일차 TIL을 작성해 보았습니다.