Java Solution: BFS using 2 queues


  • 3

    The main idea is to split all the nodes in the same level into two half.

    For the first half we insert and read from left to right.
    For the second half we insert and read from right to left.
    Then we compare each pair to see if they are same.

    public boolean isSymmetric(TreeNode root) {
        if(root==null)
            return true;
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
    
        if(!equal(root.left, root.right, q1, q2))
            return false;
        
        while(!q1.isEmpty()){
            int size=q1.size();
            while(size-->0){
                TreeNode n1 = q1.poll();
                TreeNode n2 = q2.poll();   
                if(!equal(n1.left, n2.right, q1, q2))
                    return false;
                if(!equal(n1.right, n2.left, q1, q2))
                    return false;
            }
        }
        return true;
        
    }
    
    public boolean equal(TreeNode n1, TreeNode n2, Queue<TreeNode> q1, Queue<TreeNode> q2){
        if(n1==null && n2==null)
            return true;
        if(n1==null || n2==null)
            return false;
        if(n1.val==n2.val){
            q1.add(n1);
            q2.add(n2);
            return true;
        }
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.