牛客算法题记录二（判断二叉树是否对称）

判断二叉树是否对称

• • • • 题目
      • 题解

题目

给定一棵二叉树，判断琪是否是自身的镜像（即：是否对称）
例如：下面这棵二叉树是对称的
     1
    /  \
  2      2
 / \    / \
3   4  4   3
下面这棵二叉树不对称。
     1
    / \
  2    2
    \    \
    3     3
备注：
希望你可以用递归和迭代两种方法解决这个问题
           

题解

• 1、递归

import java.util.*;
	/**
	 * TreeNode 数据结构
	 * public class TreeNode {
	 *   int val = 0;
	 *   TreeNode left = null;
	 *   TreeNode right = null;
	 * }
	 */
	public class Solution {
	    /**
	     * 用递归的方式判断
	     * 
	     * @param root TreeNode类 
	     * @return bool布尔型
	     */
	    public boolean isSymmetric (TreeNode root) {
	        if (root == null) {
	            return true;
	        }
	       return checkSymmetric(root.left, root.right);
	    }
	    
	    public boolean checkSymmetric (TreeNode left, TreeNode right) {
	    	// 如果根节点下的左右子节点都为空 对称
	        if (left == null && right == null) {
	            return true;
	        }
	        // 如果根节点下的左右子节点有一个不为空 不对称
	        if (left == null || right == null) {
	            return false;
	        }
	        // 判断左右子节点是否相等
	        // 左子节点的左子节点和右子节点的右子节点是否相等
	        // 左子节点的右子节点和右子节点的左子节点是否相等 --递归下去
	        return left.val == right.val && checkSymmetric(left.left, right.right) && checkSymmetric(left.right, right.left);
	    }
	}
           

• 2、迭代

import java.util.*;
	/**
	 * TreeNode 数据结构
	 * public class TreeNode {
	 *   int val = 0;
	 *   TreeNode left = null;
	 *   TreeNode right = null;
	 * }
	 */
	public class Solution {
	    /**
	     * 用迭代的方式判断
	     * 
	     * @param root TreeNode类 
	     * @return bool布尔型
	     */
	    public boolean isSymmetric (TreeNode root) {
	        if(root == null)
	            return true;
	        Queue<TreeNode> q = new LinkedList<>();
	        q.offer(root.left);
	        q.offer(root.right);
	 		// 循环迭代 比较
	        while(!q.isEmpty()){
	            TreeNode left = q.poll();
	            TreeNode right = q.poll();
	            if(left == null && right == null)
	                continue;
	            if(left == null || right == null)
	                return false;
	            if(left.val != right.val)
	                return false;
	 
	            q.offer(left.left);
	            q.offer(right.right);
	            q.offer(left.right);
	            q.offer(right.left);
	        }
	        return true;
	    }
	}