给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ 2 2
/ \ / 3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ 2 2
\ 3 3
有两种方法:递归和迭代。
判断两棵子树 \(p\),\(q\) 是否是对称的:首先要判断根节点,然后判断 \(p.left\) 和\(q.right\) 是否是对称的,以及 \(p.right\) 和 \(q.left\) 是否是对称的。
递归:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
boolean check(TreeNode p,TreeNode q){
if(p==null&&q==null){
return true;
}
if((p==null&&q!=null)||(p!=null&&q==null)){
return false;
}
return p.val==q.val&&check(p.left,q.right)&&check(p.right,q.left);
}
public boolean isSymmetric(TreeNode root) {
return check(root.left,root.right);
}
}
迭代:
使用队列保存值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> que=new LinkedList<TreeNode>();
que.offer(root.left);
que.offer(root.right);
while(!que.isEmpty()){
TreeNode p=que.poll(),q=que.poll();
if(p==null&&q==null){
continue;
}
if((p==null&&q!=null)||(p!=null&&q==null)||p.val!=q.val){
return false;
}
que.offer(p.left);
que.offer(q.right);
que.offer(p.right);
que.offer(q.left);
}
return true;
}
}
原文:https://www.cnblogs.com/livingsu/p/14883498.html