题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路与实现

方法1

关键：按照根节点-左结点-右结点 和按照 根节点-右结点-左结点 遍历得到的序列一致。 对于一个结点： case1：左右孩子都为空，符合对称 case2：只有一个孩子为空，不符合对称 case3：左右孩子都有，值相同，判断 左孩子的左子树与右孩子的右子树 && 左孩子的右子树与右孩子的左子树 是否对称,如果是，则为对称的

/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { boolean isSymmetrical(TreeNode pRoot) { return pRoot==null || isMirror(pRoot.left,pRoot.right); } boolean isMirror(TreeNode pleft, TreeNode pright){ if(pleft==null && pright==null)//左右孩子都为空，符合对称 return true; else if(pleft==null || pright==null)//只有一个孩子为空，不符合对称 return false; else//左右孩子都有，值相同，判断 左孩子的左子树与右孩子的右子树 && 左孩子的右子树与右孩子的左子树 是否对称,如果是，则为对称的 return (pleft.val==pright.val) && isMirror(pleft.left,pright.right)&& isMirror(pleft.right,pright.left); } }

方法2

BFS

import java.util.LinkedList; import java.util.Queue; public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot==null) return true; Queue<TreeNode> queue=new LinkedList<>() ; queue.offer(pRoot.left); queue.offer(pRoot.right); while (!queue.isEmpty()){ TreeNode t1=queue.poll(); TreeNode t2=queue.poll(); if(t1==null && t2==null) continue; if(t1==null || t2==null) return false; if(t1.val!=t2.val) return false; queue.add(t1.left); queue.add(t2.right); queue.add(t1.right); queue.add(t2.left); } return true; } }