[코딩연습] Symmetric Tree 트리가 대칭인지 확인

LeetCode 문제 중 난이도 Easy인 Symmetric Tree이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

주어진 이진 트리를 가지고 해당 트리가 거울에 비친 자신과 같은지(가운데를 중심으로 대칭인지) 판별하라.

트리는 모든 노드들이 연결되어있고 순환이 존재하지 않는 그래프이다.

나무(tree)를 거꾸로 그린 모양의 계층구조를 생각해보자. 트리(tree) 자료구조는 뿌리(root node)에서 시작해 가지가 뻗어 나가며 맨 끝에는 잎(leaf node)이 달려 있다. 우리가 잘 아는 트리구조가 있는데 바로 회사의 조직도와 컴퓨터 디렉토리이다.

아래 그림은 이진 트리(binary tree)의 예이다. 예시를 보며 몇가지 기본적인 트리 용어를 알아보자.

* 이진트리(binary tree) : 트리 중에서 각 노드의 자식 노드의 수가 2개 이하인 트리

Node(A,B,C...J) : 트리의 구성요소에 해당하는 요소들

Root Node(A) : 최상위 노드

Parent Node : 어떤 노드의 상위 노드

A는 B와 C의 부모노드이고 B와 C도 각각 D&E, F&Gd의 부모노드이다

Child Node : 어떤 노드의 하위 노드

F와 G는 C의 자식노드이고 H와 I는 E의 자식노드이다

Subtree : 어떤 노드의 부모 노드의 집합

D의 조상은 B,A이고 J의 조상은 G,C,A이다

Descendant of a node : 어떤 노드의 자식노드들의 집합

C의 자손은 F,G,J이고 A의 자손은 자기자신을 제외한 전체 노드들이다

Leaf Node(D,H,I,F,J) : 자식노드가 존재하지 않는 노드

Subtree : 어떤 트리의 안에 있는 작은 트리

트리 T의 서브트리 S는 T의 노드 중 하나와 그의 자손들로 이루어진 트리

Depth of a node : 어떤 노드의 루트노드까지의 조상의 수

루트노드의 depth는 0이고 G의 depth는 2이다

Height of a tree : 해당 트리가 가진 노드들의 depth중 최댓값

다시 문제로 돌아가보자. 트리가 좌우 대칭이려면 루트노드를 중심으로 왼쪽 서브트리를 좌우대칭한 것이 오른쪽 서브트리와 같아야 한다. 그러려면 왼쪽 서브트리의 왼쪽 자식노드와 오른쪽 서브트리의 오른쪽 자식노드의 값이 같아야 하고 왼쪽 서브트리의 오른쪽 자식노드와 오른쪽 서브트리의 왼쪽 자식노드의 값이 같아야 한다.

같은방식으로 자손노드들을 리프노드까지 탐색한다. 코드로 나타내면 다음과 같다.

class Solution {
    public boolean isSymmetric(TreeNode root) {
        
        return isMirror(root,root);
    }
    
    public boolean isMirror(TreeNode t1, TreeNode t2) {
        
        //t1과 t2가 둘다 null이면 true
        if(t1 == null && t2 == null) return true;
        
        //t1,t2중에 하나만 널이면 양쪽이 같지 않으므로 false
        if(t1 == null || t2 == null) return false;
        
        //t1과 t2의 값이 달라도 false
        if(t1.val != t2.val) return false;
        
        return isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);
    }
}

13번째 줄의 (t1 == null || t2 == null)는 위에서 이미 둘다 null인 경우를 체크했으므로 t1이나 t2가 둘중 하나만 null인 경우를 체크한다.

이 방법의 시간복잡도는 O(n)이고 공간복잡도의 worse case는 트리가 일직선으로 이루어져 Height가 O(n)인 경우이므로 O(n)이다.

문제 출처 - https://leetcode.com/problems/symmetric-tree/