Concise Java solution using one queue


  • 0

    There are two key points here:

    • We should always operate on two nodes that are counterparts.

    • In the queue we need to make sure two mirror nodes are next to each other so when we poll two nodes we can always get a pair of mirror nodes.

    public class Solution {
        public boolean isSymmetric(TreeNode root) {
            if(root==null) return true;
            Queue<TreeNode> q = new LinkedList<>();
            
            if(!insertNodes(root.left, root.right, q)) return false;
            while(!q.isEmpty()){
                TreeNode n1 = q.poll();
                TreeNode n2 = q.poll();
                if(!insertNodes(n1.left, n2.right, q) || !insertNodes(n1.right, n2.left, q)) return false;
            }
            
            return true;
        }
        
        public boolean insertNodes(TreeNode n1, TreeNode n2, Queue<TreeNode> q){
            if(n1==null && n2==null) return true;
            if(n1==null || n2==null || n1.val!=n2.val) return false;
            q.add(n1);
            q.add(n2);
            return true;
        }
    }
    
    

Log in to reply
 

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