[LeetCode] 101. Symmetric Tree

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

Symmetric Tree - LeetCode

 

 

 

1. 문제 설명 

root Node를 기준으로 left Node와 right Node가 서로 대칭(symmetric)한가를 판별하는 문제이다.

 

 

2. 접근 방식 

그렇게 어렵지 않은 문제라고 생각했는데 node들을 넣고 빼는 순서가 꼬여서 많이 애먹었다..... 

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

/**
 * 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;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true; // 그냥 null
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root.left); q.add(root.right);
        while(!q.isEmpty()) {
            TreeNode left, right;
            left = q.poll(); right = q.poll();
            if(left == null && right == null) continue;
            if(left == null || right == null || left.val != right.val) return false;
            q.add(left.left); q.add(right.right);
            q.add(left.right); q.add(right.left);
        }
        return true;
    }
}

 

 

4. 분석 및 시간복잡도 

시간 복잡도 : O(nlogn)