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

剑指offer算法题

树

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

题目分析 方法一 非递归 DFS层次遍历，每次取出一对节点，放入节点的时候，放入左节点的左节点和右节点的右节点，以及左节点的右节点和右节点的左节点。节点为null也同样放入。如果取出是遇到左右节点同时为null的时候，说明此处对称，跳出本次循环。

下面是Java代码

import java.util.Queue; import java.util.LinkedList; public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null){ return true; } Queue<TreeNode> q = new LinkedList<>(); q.offer(pRoot.left); q.offer(pRoot.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; } }

方法二 递归 递归返回条件为当前两个节点的值是否相等&&左节点的左节点与右节点的右节点是否对称&&左节点的右节点与右节点的左节点是否对称的结果。 下面是Java代码

public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null){ return true; } return isSame(pRoot.left, pRoot.right); } private boolean isSame(TreeNode left , TreeNode right){ if(left == null && right == null){ return true; } if(left == null || right == null){ return false; } return left.val == right.val && isSame(left.left,right.right)&&isSame(left.right,right.left); } }

参考https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&&tqId=11211&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking