Leetcode 101) Symmetric Tree

30 Jul 2021 in Algorithms

내 답안

• root를 기준으로 두개의 queue를 가진다.
• 두번째 queue에 노드를 추가해 줄 때 right left 순으로 추가해준다.

/**
 * 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) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();

        q1.add(root.left);
        q2.add(root.right);

        while(!q1.isEmpty()){
            int size1 = q1.size();
            int size2 = q2.size();
            Stack<Integer> s= new Stack<>();

            if(size1!=size2){return false;}

            for(int i=0;i<size1;i++){
                TreeNode a= q1.poll();
                TreeNode b= q2.poll();
                if(a==null && b==null){continue;}
                if(a==null || b==null){return false;}
                if(a.val!=b.val){return false;}
                q1.add(a.left);q1.add(a.right);
                q2.add(b.right);q2.add(b.left);
            }

        }

        return 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;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {


        return isMirror(root.left,root.right);
    }


    private boolean isMirror(TreeNode n1,TreeNode n2){
        if(n1==null && n2==null) return true;
        if(n1==null || n2==null) return false;
        if(n1.val!=n2.val) return false;

        return isMirror(n1.left,n2.right) && isMirror(n1.right,n2.left);
    }
}