Two solutions of leetcode101 symmetric binary tree (recursion and iteration)

 

  The symmetry mentioned here is axial symmetry , in other words , The left child of the left subtree should be the same as the right child of the right subtree , Left subtree right child is the same as right subtree left child .

Here is the recursive method ：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        
        if(root==null){
            return true;
        }
            return deep(root.left,root.right);
         }   


         public boolean deep(TreeNode left,TreeNode right){
             if(left==null&&right==null){
                 return true;// Empty is true 
             }if(left==null||right==null){
                 return false;// If one is empty, it is false 
             }if(left.val!=right.val){
                 return false;// Inequality is false 
             }
             return deep(left.left,right.right)&&deep(left.right,right.left);// recursive   Left subtree left child and right subtree right child comparison , Left subtree right child and right subtree left child comparison .
         }
    }

Iterative method ：

class Solution {
	public boolean isSymmetric(TreeNode root) {
		if(root==null || (root.left==null && root.right==null)) {
			return true;
		}
		// Save node with queue 
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		// Put the left and right children of the root node in the queue 
		queue.add(root.left);
		queue.add(root.right);
		while(queue.size()>0) {
			// Take two nodes out of the queue , Then compare the two nodes 
			TreeNode left = queue.removeFirst();
			TreeNode right = queue.removeFirst();
			// If both nodes are empty, continue the loop , If one of them is empty, it returns false
			if(left==null && right==null) {
				continue;
			}
			if(left==null || right==null) {
				return false;
			}
			if(left.val!=right.val) {
				return false;
			}
			// The left child of the left node ,  Put the right child of the right node into the queue 
			queue.add(left.left);
			queue.add(right.right);
			// The right child of the left node , The left child of the right node is put in the queue 
			queue.add(left.right);
			queue.add(right.left);
		}
		
		return true;
	}
}