Java 1ms recursive solution and 2ms iterative solution


  • 3
    R

    Recursive:

        public boolean isSymmetric(TreeNode root) {
    		if (root == null)
    			return true;
    		if (root.left != null && root.right != null) {
    			if (root.left.val != root.right.val)
    				return false;
    		}
    		return isSymmetric(root.left, root.right);
    	}
    	
    	private boolean isSymmetric(TreeNode t1, TreeNode t2) {
    		if (t1 == null && t2 == null)
    			return true;
    		if (t1 == null || t2 == null)
    			return false;
    		boolean isLeftSymmetric = isSymmetric(t1.left, t2.right);
    		boolean isRightSymmetric = isSymmetric(t1.right, t2.left);
    		return (t1.val == t2.val) && isLeftSymmetric && isRightSymmetric;
    	}
    

    Iterative:

    public boolean isSymmetric(TreeNode root) {
    		if (root == null)
    			return true;
    		
    		Queue<TreeNode> left = new LinkedList<>();
    		Queue<TreeNode> right = new LinkedList<>();
    		left.add(root.left);
    		right.add(root.right);
    		while(!left.isEmpty() && !right.isEmpty()) {
    			TreeNode l = left.poll();
    			TreeNode r = right.poll();
    			
    			if (l == null && r == null)
    				continue;
    			if (l == null || r == null)
    				return false;
    			
    			if (l.val != r.val)
    				return false;
    			
    			left.add(l.left);
    			right.add(r.right);
    			
    			left.add(l.right);
    			right.add(r.left);
    		}
    		
    		if (left.isEmpty() && right.isEmpty())
    			return true;
    		else 
    			return false;
    	}

Log in to reply
 

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