Share my recursively and iteratively java solution


  • 0
    C
    //recursive : 1ms
    public boolean isSymmetric(TreeNode root) {
        return root == null || isSymmetricHelper(root.left, root.right);
    }
    public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
        if(left == null || right == null)
        	return left == right;
        return left.val == right.val && isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
    }
    
    //iterator : 1ms
    public boolean isSymmetric(TreeNode root) {
    	if(root == null) return true;
    	Queue<TreeNode> queue = new LinkedList<>();
    	TreeNode left = root.left;
    	TreeNode right = root.right;
    	if(left == null || right == null) return left == right;
    	queue.add(left);
    	queue.add(right);
    	while(!queue.isEmpty()){
    		left = queue.poll();
    		right = queue.poll();
    		//check value
    		if(left.val != right.val) return false;
    		//check structure : part 1
    		if(left.left != null && right.right != null){
    			queue.add(left.left);
    			queue.add(right.right);
    		}
    		else if(!(left.left == null && right.right == null)){
    			return false;
    		}
    		//check structure : part 2
    		if(left.right != null && right.left != null){
    			queue.add(left.right);
    			queue.add(right.left);
    		}
    		else if(!(left.right == null && right.left == null)){
    			return false;
    		}
    	}
    	return true;
    }

  • 0
    I

    It is a very elegant iterator solution. Just make while loop a little bit simplify.
    while(!queue.isEmpty()) {
    TreeNode left = queue.poll();
    TreeNode right = queue.poll();
    if ((left == null && right != null) || (left != null && right == null)) {
    return false;
    }
    if (left != null & right != null) {
    if (left.val != right.val) {
    return false;
    }
    queue.offer(left.left);
    queue.offer(right.right);
    queue.offer(left.right);
    queue.offer(right.left);
    }
    }


Log in to reply
 

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