Easy to understand Solutions (both Iterative & Recursive)


  • 0
    E

    Recursive method is quite straightforward:

    public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        
        return isSymmetric(root.left, root.right); 
    }
    
    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if(left==null && right==null) return true;
        if(right==null || left==null) return false;
        
        return left.val==right.val  
            && isSymmetric(left.left, right.right) 
            && isSymmetric(left.right, right.left);
    }
    }
    

    For the iterative method, I used two queues, and do a BFS on both of them. Code is as follows:

    public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left==null && root.right==null) ) return true;
        if(root.left==null || root.right==null) return false;
        
        Queue<TreeNode> qLeft = new LinkedList<>(); // queue for left subtree
        Queue<TreeNode> qRight = new LinkedList<>(); // queue for right subtree
        
        qLeft.add(root.left);
        qRight.add(root.right);
        while(!qLeft.isEmpty() || !qRight.isEmpty()) {
            if(qLeft.isEmpty() || qRight.isEmpty()) return false;
            int size = qLeft.size();
            for(int i=0; i<size; i++) {
                TreeNode currentLeft = qLeft.peek();
                qLeft.poll();
                TreeNode currentRight = qRight.peek();
                qRight.poll();
                if( (currentLeft==null && currentRight!=null) 
                    || (currentRight==null && currentLeft!=null) ) return false; // not sure why this line is needed...
                if(currentLeft.val != currentRight.val) return false;
                if( (currentLeft.left==null && currentRight.right!=null)
                    || (currentLeft.right==null && currentRight.left!=null) ) return false;
                if(currentLeft.left!=null)
                    qLeft.add(currentLeft.left);
                if(currentLeft.right!=null)
                    qLeft.add(currentLeft.right);
                if(currentRight.right!=null)
                    qRight.add(currentRight.right);
                if(currentRight.left!=null)
                    qRight.add(currentRight.left);
            }
        }
        return true;
    }
    }

Log in to reply
 

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