[LeetCode/101/Java]Symmetric Tree

[LeetCode/101/Java]Symmetric Tree

풀이

/**
 * 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) {
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        if(left == null && right == null) return true;
        if((left == null && right != null) || (left != null && right == null)) return false;
        
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        
        queue1.offer(left);
        queue2.offer(right);
        
        while(!queue1.isEmpty() && !queue1.isEmpty()) {
            if(queue1.size() != queue2.size()) return false;
             for(int i = 0; i < queue1.size(); i++) {
                 TreeNode cur1 = queue1.poll();
                 TreeNode cur2 = queue2.poll();

                 if(cur1 == null && cur2 == null) continue;
                 if(cur1 == null || cur2 == null) return false;
                 if(cur1.val != cur2.val) return false;
                 
                 queue1.offer(cur1.left);
                 queue1.offer(cur1.right);
                 queue2.offer(cur2.right);
                 queue2.offer(cur2.left);
             }
        }
        return true;
    }
}

후기

양쪽의 노드가 대칭인지 아닌지를 판단하는 알고리즘입니다.

대칭일 경우에는 true를 반환합니다.

넓이우선탐색(BFS)를 이용해서 좌우의 값을 반대로 큐에 담아서 비교하는 방식을 사용했습니다.

 

time complexity O(N)
space complexity O(N2)