리트코드 - 101. Symmetric Tree

리트코드 - 101. Symmetric Tree

출처 - https://leetcode.com/problems/symmetric-tree/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

이진 트리의 루트가 주어지면 그것이 자신의 거울인지(즉, 중심을 중심으로 대칭인지) 확인합니다.

 

의사코드

함수 isSymmetric if (root == null)     true 리턴 isSymmetric(root의 left, root의 right) 함수끝 함수 isSymmetric(왼쪽노드,오른쪽 노드) 매개변수 두개로 오버로딩 if (leftNode == null && rightNode = null)     true 리턴 if (둘중에 하나가 null인 경우)    false 리턴 if (leftNode의 값 != rightNode의 값)     false 리턴 isSymmetric(leftNode의 왼쪽, rightNode의 오른쪽) && isSymmetric(leftNode의 오른쪽, rightNode의 왼쪽) 리턴 함수끝

 

풀이코드

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

        return isSymmetric(leftNode.left, rightNode.right) && isSymmetric(leftNode.right, rightNode.left);
    }
}

코드설명

노드가 root 를 기준으로 좌우 대칭인지 묻는 문제이다.

재귀적으로 구현하고자 할때, 처음에는 좌우만 따지면 되지만 그 이후에는 좌우를 반대로 따져야 하기 때문에 주어진 함수로 해결이 어려울것 같아 매개변수 두개로 오버로딩 했다.

 

먼저 root를 기준으로 leftNode와 rightNode를 확인하는데 둘다 null인 경우 대칭이므로 true를 리턴한다.

그리고 한쪽만 null인 경우 대칭이 깨지므로 false를 리턴한다.

마지막으로 둘다 null이 아닌 경우 val 값을 비교해서 같지 않으면 false를 리턴한다.

이렇게 첫번째 검증이 끝나면 자식 노드에 대해서는 각각 반대로 이동해야 한다.

그림과 같이 왼쪽 노드는 왼쪽으로 가서 확인해야 하고 이때 오른쪽 노드는 오른쪽을 확인해야 한다.

반대의 경우도 마찬가지다.

 

이동한 노드를 가지고 똑같이 오버로딩한 함수로 재귀적으로 검증을 하면 노드가 대칭을 이루는지 확인할 수 있다.

 

시간복잡도 - O(n)

공간복잡도 - O(n)

 

문제를 풀며 생각한 흐름과 배운 점

리팩토링

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

        return isSymmetric(leftNode.left, rightNode.right) && isSymmetric(leftNode.right, rightNode.left);
    }
}

중간에 if문을 더 줄였다.

생각해보면 이미 처음 if문에서 left와 right 둘다 null인 경우를 처리하고 있기 때문에 두번째 if문에서는 하나만 null이면 바로 false가 된다.

 

runtime도 0ms이고, Memory도 상위권이라 만족스러운 코드가 되었다.(생각하는데 힘들었던 건 비밀..)

다른 사람 코드도 거의 비슷한 것 같다.

 

정리

노드가 대칭인지 확인하는 방법