Today I Learned

오늘도 leetcode에서 코테를 열심히 풀었다.

101. Symmetric Tree

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

문제

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Input: root = [1,2,2,3,4,4,3]
Output: true

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

풀이방법

• 양쪽을 나눠서 bfs 방식으로 가되 서로 대칭되도록 매칭만 시켜주면 쉽게 풀릴 것 같았다.

• 우선 edgecase 예외 처리를 미리 다 해준다.

• 왼쪽큐와 오른쪽큐를 따로 만든다.

• 왼쪽 큐에는 루트의 왼쪽노드부터 왼쪽-오른쪽 순서로 큐에 집어넣고, 오른쪽 큐에는 루트의 오른쪽노드부터 오른쪽-왼쪽 순서로 큐에 집어넣는다.

• while문으로 반복을 시키면서 큐에서 꺼내면서 매칭 시키는데 값이 맞지 않거나, 한쪽만 null이면 바로 대칭이 깨지므로 false를 반환시킨다.

• bfs 방식으로 차근차근 매칭시키다가 while문이 끝나면 대칭이므로 true를 반환하고 완료!

Java 코드

class Solution {
  public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> qr = new ArrayDeque<>();
    Queue<TreeNode> ql = new ArrayDeque<>();

    if (root==null||(root.right==null&&root.left==null)) return true;

    if ((root.right!=null&&root.left==null)||(root.right==null&&root.left!=null)) return false;

    TreeNode rn = root.right;
    TreeNode ln = root.left;

    if (rn.val!=ln.val) return false;

    qr.add(rn);
    ql.add(ln);

    while (!qr.isEmpty() || !ql.isEmpty()){
      ln = ql.poll();
      rn = qr.poll();

      if ((ln.left==null&&rn.right!=null)||(ln.left!=null&&rn.right==null)
          ||(ln.right==null&&rn.left!=null)||(ln.right!=null&&rn.left==null)){
        return false;
      }

      if (ln.left!=null&&rn.right!=null){
        if (ln.left.val != rn.right.val) return false;
        ql.add(ln.left);
        qr.add(rn.right);
      }

      if (ln.right!=null&& rn.left!=null){
        if (ln.right.val != rn.left.val) return false;
        ql.add(ln.right);
        qr.add(rn.left);
      }
    }
    return true;


  }
}

더 나은 해답

leetcode는 문제를 풀고나면 Runtime과 Memory를 분석해 시간&공간복잡도에서 상위 몇%인지 분석이 나온다.
내 답변은 하위권으로 훨씬 더 간단한 답안이 존재했다.

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) 
            return true;
        
        return isSymmetric(root.left, root.right);
    }
    
    boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) 
            return true;

        if (left == null || right == null) 
            return false;

        if (left.val != right.val) 
            return false;

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

• 메서드를 따로 분리해 재귀 방식으로 해결한 방법이다.

• 좌우가 다 null이면 true, 한쪽만 null이면 false, 값이 다르면 false.
  반환값으로 좌좌우우, 좌우우좌를 비교해 재귀로 구현하면 완료.

• 간단한 문제인데 너무 꼬아서 생각했던것 같다. leetcode 문제 퀄리티가 꽤나 괜찮아 보인다. 앞으로 꾸준하게 풀면서 실력을 길러보자!!