LeetCode: 101번 (Symmetric Tree) [JAVA]

문제 링크

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

Symmetric Tree - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 대칭을 체크하기 위한 재귀 기반 함수를 구현(인자로는 node 2개 -> node1, node2)
   1) 만약 주어진 노드 2개 중 한 쪽만 null이라면 false를 반환, 모두 null이라면 true를 반환
   2) 만약 노드 2개의 값이 다르다면 false 반환
   3) 이후엔 두 재귀 기반 함수 결과값의 AND 값을 반환하는데, 한 쪽은 node1의 왼쪽과 node2의 오른쪽을 인자로, 다른 한 쪽은 node1의 오른쪽과 node2의 왼쪽을 인자로 삼음
   
2. 주어진 트리의 루트 노드에서, 해당 노드의 왼쪽과 오른쪽을 인자로 앞선 재귀 함수를 호출하여 그 결과를 반환

 주어진 트리가 대칭인지를 확인하기 위해, 재귀 기반으로 대칭성을 검증할 수 있다. 대칭이 맞는 지를 확인하기 위해선 당연히 루트 노드를 제외하며, 이후엔 하위 두 노드를 비교해 나가면 된다. 이 때 우선적으로 두 노드를 비교하며, 이 두 노드의 비교가 끝난 후엔 해당 두 노드의 하위 노드들을 또 다시 비교해주면 된다. 이 경우 노드 1의 왼쪽과 오른쪽, 노드 2의 왼쪽과 오른쪽 이렇게 4개의 노드가 생기는데, 이들을 비교할 때 대칭을 위해 서로 다른 방향의 노드를 비교해야 한다. 노드 1의 왼쪽과 노드 2의 오른쪽, 노드 1의 오른쪽과 노드 2의 왼쪽을 비교해야 대칭을 확인할 수 있다. 
 물론 이 과정에서 끝이 아닌, 트리 형태로 노드들이 끝없이 이어지기 때문에 이를 재귀 함수 기반으로 해결해야 한다. 해당 함수의 인자는 노드 2개이며, 우선 노드 2개에 대한 대칭을 확인한다. 두 노드 중 한 쪽만 null이라면 대칭이 아니기 때문에 false를 반환하고, 둘 다 null이라면 대칭이기 때문에 true를 반환한다. 그 다음엔 두 노드의 값을 비교해, 만약 값이 다르다면 false를 반환한다. 최종적으로 두 노드가 대칭인 지 확인을 마쳤다면, 해당 하위 노드들의 대칭을 비교하면 된다. 노드 1의 왼쪽과 노드 2의 오른쪽, 노드 1의 오른쪽과 노드 2의 왼쪽을 재귀함수를 통해 비교하여, 그 둘의 결과를 AND 연산하여 반환한다.
 이렇게 구현한 재귀함수를 바탕으로, 주어진 트리의 루트 노드에 대해 그 노드의 하위 왼쪽 노드와 오른쪽 노드를 인자로 재귀함수를 호출하여 그 결과를 반환하면 된다.

 

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return checkSymmetric(root.left, root.right);
    }

    boolean checkSymmetric(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            if (node1 == null && node2 == null) {//양쪽 노드 모두 null이면
                return true;
            } else {//한 쪽만 null이면
                return false;
            }
        }

        if (node1.val != node2.val) {//값이 다르면
            return false;
        } else {//값이 같다면, node1의 왼쪽/node2의 오른쪽, node1의 오른쪽/node2의 왼쪽을 비교한 결과를 AND 연산해 반환
            return (checkSymmetric(node1.left, node2.right) && (checkSymmetric(node1.right, node2.left)));
        }
    }
}

결과