[99클럽 코테 스터디] 14일차 TIL - Symmetric Tree

오늘의 학습 키워드

• Symmetric Tree

공부한 내용 본인의 언어로 정리하기

/**
 * 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);
    }
    
    private boolean isMirror(TreeNode left, TreeNode right) {
        
        //두 값이 모두 null일 경우 같으므로 true 반환
        if (left == null && right == null) {
            return true;
        }
        
        //left 또는 right 둘 중 하나의 값이 null일 경우 NullPointerException이 발생하는 오류가 있었음
        if(left == null || right == null) {
            return false;
        }
        
        //각각 chech로 비교하는 것 보다 isMirror로 사용하는 것이 명시적으로 알아보기 더 좋을 것 같아서 사용하였음
        return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }
}

오늘의 회고

오늘은 이진 탐색 트리를 이어서 Symmetric Tree(대칭 트리)의 문제가 나왔다. 오늘은 어제 이진 탐색 트리와 노드에 대해서 살짝이나마 공부를 하고 나서 그런지 양 쪽의 값을 비교해서 맞으면 true를 반환하고 아니면 false를 반환해야겠다는 생각이 바로 들었다. 그래서 처음 적혀있는 코드에 상위 root가 같은 경우 true를 반환해주고 하위 루트를 비교하는 방향으로 만들었다.

public boolean isSymmetric(TreeNode root) {
	if (root == null) {
		return true;
	}
	return isMirror(root.left, root.right);
}

그리고 하위 노드들을 비교하기 위한 isMirror 메서드를 생성하였다. 이 메서드는 재귀적 접근법을 사용하여 트리의 대칭성을 확인할 수 있다.
트리의 모든 레벨을 탐색하여 올바른 값을 반환해주기 위하여
양쪽의 노드가 같은 경우 true를 반환해주어야 했다.
그리고 isMirror 메서드를 사용해 3개의 경우의 수를 모두 비교해서 값을 반환해 주어야했다.

private boolean isMirror(TreeNode left, TreeNode right) {
        
        //두 값이 모두 null일 경우 같으므로 true 반환
        if (left == null && right == null) {
            return true;
        }
        
        //각각 chech로 비교하는 것 보다 isMirror로 사용하는 것이 명시적으로 알아보기 더 좋을 것 같아서 사용하였음
        return (left.val == right.val) && isMirror(left.left, right.right) && isMirror(left.right, right.left);
    }

이렇게 실행했더니 NullPointException이 나왔고 left 또는 right 둘 중의 하나의 값이 null일 경우 NullPointException이 발생한다는 것을 알았고 함수를 추가해주었다.

//left 또는 right 둘 중 하나의 값이 null일 경우 NullPointerException이 발생하는 오류가 있었음
(left == null || right == null) {
	return false;
}

AI 코드리뷰

현재 코드의 장점

1. 명확한 논리 구조: 코드가 명확하게 작성되어 있어, 트리가 대칭인지 확인하는 로직을 이해하기 쉽습니다.
2. 적절한 조건 검사: null 체크와 left.val과 right.val의 비교 등 필수적인 조건을 잘 검사하고 있습니다.
3. 재귀 사용: 재귀를 통해 대칭성을 검사하는 방식은 매우 직관적이며, 이진 트리의 대칭성을 확인하는 데 적합합니다.

현재 코드의 단점

1. 코드 중복: isMirror 메서드 내의 조건 검사 코드가 다소 중복되어 보입니다. 이를 간단하게 할 수 있는 방법이 있습니다.
2. 명명 규칙: isMirror 메서드의 이름이 적절하긴 하지만, 대칭성을 확인하는 다른 이름으로 더 명확히 할 수 있습니다.

시간 복잡도

시간 복잡도: O(n)

• 각 노드는 한 번씩 방문되며, 각 노드에서 O(1) 시간 내에 값을 비교하고 재귀 호출을 수행합니다.
• 트리의 모든 노드를 방문하기 때문에 시간 복잡도는 O(n)입니다.
  공간 복잡도: O(h)
• 재귀 호출 스택의 깊이는 트리의 높이에 비례합니다.
• 최악의 경우 트리가 한쪽으로 치우쳐 있을 때, 공간 복잡도는 O(n)입니다. 하지만 균형 잡힌 트리에서는 O(log n)입니다.

개선된 코드 제안

내 코드와 계속 같은 코드를 제시해 주어서 더 효율적인 방법으로 시간복잡도를 줄여서 만들어달라고 해보았다.

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root.left);
        queue.add(root.right);
        
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null || left.val != right.val) {
                return false;
            }
            
            queue.add(left.left);
            queue.add(right.right);
            queue.add(left.right);
            queue.add(right.left);
        }
        
        return true;
    }
}

개선된 버전의 장점:

1. 스택 오버플로우 방지: 재귀 호출이 아닌 반복을 사용하여 함수 호출 스택을 관리함으로써, 큰 트리에서도 스택 오버플로우를 방지할 수 있습니다.
2. 명확한 구조: 반복 구조를 사용하여 코드를 작성하면, 트리의 각 노드를 한 번씩만 방문하게 됩니다.
3. 시간 복잡도는 여전히 동일합니다:

시간 복잡도: O(n)

• 반복 구조를 사용하여 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다.
  공간 복잡도: O(n)
• 큐를 사용하여 노드를 저장하므로, 최악의 경우 큐에 저장된 노드의 수는 트리의 너비와 같습니다.
• 완전 이진 트리의 경우 공간 복잡도는 O(n/2) ≈ O(n)입니다.

---

내일 공부할 것 :

1. 이진 트리와 트리 탐색 알고리즘: 이진 트리의 기초 및 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 알고리즘에 대해 공부해보세요. 이들은 트리 구조를 이해하고 조작하는 데 필수적입니다.
2. 재귀 함수: 재귀 함수의 원리와 다양한 재귀적 알고리즘에 대해 학습해보세요. 재귀의 효율성과 한계를 이해하는 것이 중요합니다.
3. 예외 처리: Java에서의 예외 처리와 NullPointerException 같은 일반적인 예외를 어떻게 다루는지에 대해 공부해보세요. 이는 코드의 안정성과 신뢰성을 높이는 데 도움이 됩니다.
4. 테스트 케이스 작성: 다양한 입력에 대해 코드가 제대로 작동하는지 확인하기 위해 대칭 트리에 대한 다양한 테스트 케이스를 작성해보세요. 이는 코드의 견고성을 높이는 데 필수적입니다.

문제

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