LeetCode#101

Symmetric Tree

Posted by Start Bootstrap on November 24, 2019 · 3 mins read

문제

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

이진 트리가 주어지면 그것이 자신의 거울인지 (즉, 중심을 기준으로 대칭인지) 확인하십시오.

예를 들어 이진 트리 [1,2,2,3,4,4,3]은 대칭입니다.

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

그러나 다음 [1,2,2, null, 3, null, 3]은 아닙니다 :

    1
   / \
  2   2
   \   \
   3    3

Note : Bonus points if you could solve it both recursively and iteratively.

재귀적으로 반복적으로 해결할 수 있다면 보너스 포인트.

기본 지식

재귀호출(recursive call) :

  • 재귀호출이란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미합니다.

  • 재귀함수를 작성할 때는 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때 까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료조건(stop condition)이 꼭 포함 되어야한다는 부분을 인지하고 작성하여야 무한로프를 방지할 수 있습니다.

풀이

대칭이 되려면 서브 트리의 왼쪽과 오른쪽 또는 그 반대 오른쪽과 왼쪽이 같은지를 비교해야 합니다.

        1
    /       \
  2(a)     2(b)
 /    \    /   \
3      4  4     3

루트(1)를 제외하고 2(a)의 왼쪽(3)과 2(b)의 오른쪽(3)이 같고, 2(a)의 오른쪽(4)과 2(b)의 왼쪽(4)이 같아야 합니다.

그리고 이 문제 풀이에서 중요한 것은, 같다면 true를 return 하는 것이 아니고, false를 찾아내서 return하고 끝까지 false가 없다면 true를 return하는 방식으로 대칭을 확인합니다. 이유는 같아서 true를 return 한다면 그 다음은 대칭인지 확인하지 않고 true로 결과를 나타내기 때문일 것입니다.

즉, true를 찾는 과정이 아닌 false를 찾아내는 과정이며, 끝까지 false가 없다면 true(대칭)인 것 입니다.

Answer :

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true; 
        return compare(root.left, root.right);        
    }
    public boolean compare(TreeNode left, TreeNode right){
        if( left == null  && right == null ) return true; //a
        if( left == null  || right == null ) return false; //b
        if( left.val != right.val ) return false; //c
        return compare( left.left, right.right ) && compare( left.right, right.left);
    }
}
  1. root가 null인 상황은 그냥 true를 return합니다.
  2. compare(root.left, root.right)로 비교를 시작합니다.
  3. a가 위에서 설명했듯이, 끝까지 false가 없어서 true를 return한 상황입니다. (재귀호출을 하며 false인 상황이 하나라도 발견된다면 false를 return할 것입니다.)
  4. b는 left,right 둘 중 하나가 null이면 false를 return해서 예외사항(null Exception)을 처리해 줍니다. (둘다 null인 상황은 위에서 걸림)
  5. c는 해당 노드의 값을 비교했을 때 다르면 false를 return 합니다.
  6. 그 후 다시 재귀호출.

위 문제의 재귀호출 stop condition은 모든 경우의 수에 대해 return하게 함으로써, 무한로프를 방지 합니다.

출처 : 제가 알고리즘 문제에 막 감을 익히고 있는 단계여서 유튜버 승지니어님의 코드를 많이 인용하였습니다. 도움되는 영상이 많이 있으므로 많은 방문 부탁드리겠습니다.

유튜브 승지니어 해당영상

← Previous Post Next Post →