[Algorithm/Java][LeetCode] 101. Symmetric Tree

[LeetCode] 101. Symmetric Tree

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

문제 접근

루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리가 대칭인지를 파악하는 문제이다.
BFS처럼 큐를 이용해서 반복문으로 풀려고 했으나, 뭔가 잘 안되서 재귀함수를 이용했다.
왼쪽과 오른쪽 서브트리의 노드를 재귀 함수를 이용해 비교
나올 수 있는 경우의 수 4가지
1. 양쪽 노드가 모두 null인 경우(아무 문제 없이 끝까지 트리를 순회 헀으므로 true)
2. 한쪽 노드만 null인 경우(비대칭이므로 false)
3. 양쪽 노드의 값이 다른 경우(비대칭이므로 false)
4. 양쪽 노드의 값이 같은 경우(지금까지는 대칭이므로 추가적인 트리 순회 - 재귀 함수를 이용해 왼쪽,오른쪽 자식들을 순회)
-> 왼쪽과 오른쪽 모두 true일 경우만 대칭이므로 마지막에 return left&&right 추가

Code

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

어려웠던 점 / 배운 점 / 느낀 점

처음에 왼쪽과 오른쪽 서브트리를 queue를 이용해 풀려고 했는데 잘 안되서 실패했다.
그리고 재귀함수를 이용해서 풀었는데 처음에는 return left && right가 없어서 계속 실패했고
계속 println을 이용해서 찍어서 거의 찍어서 맞춘 급으로 모든 경우의 수를 다 해본 것 같다.