例如： 下面这棵二叉树是对称的
下面这棵二叉树不对称。
数据范围：节点数满足 
，节点上的值满足 
要求：空间复杂度 )
，时间复杂度
备注：
你可以用递归和迭代两种方法解决这个问题
[编程题]对称的二叉树
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
TreeNode root = mirrorCopyRec(pRoot);
if(isSameTree(root,pRoot))
return true;
return false;
}
//不破坏原来的二叉树，新建一个原来二叉树的镜像二叉树
TreeNode mirrorCopyRec(TreeNode pRoot)
{
if(pRoot==null)
return pRoot;
TreeNode root = new TreeNode(pRoot.val);
root.left = mirrorCopyRec(pRoot.right);
root.right = mirrorCopyRec(pRoot.left);
return root;
}
//判断两个二叉树是否相等
boolean isSameTree(TreeNode first,TreeNode second)
{
if (first == null && second == null) {
return true;
}
// 如果其中一棵树为空，则不同
else if (first == null || second == null) {
return false;
}
// 如果两颗谁都不为空，则判断左右子树是否相同
if (first != null && second != null) {
if (first.val != second.val)
return false;
else
return isSameTree(first.left, second.left) && isSameTree(first.right, second.right);
}
return false;
}
}
boolean isSymmetrical(TreeNode pRoot)
{
TreeNode root = mirrorCopyRec(pRoot);
if(isSameTree(root,pRoot))
return true;
return false;
}
//不破坏原来的二叉树，新建一个原来二叉树的镜像二叉树
TreeNode mirrorCopyRec(TreeNode pRoot)
{
if(pRoot==null)
return pRoot;
TreeNode root = new TreeNode(pRoot.val);
root.left = mirrorCopyRec(pRoot.right);
root.right = mirrorCopyRec(pRoot.left);
return root;
}
//判断两个二叉树是否相等
boolean isSameTree(TreeNode first,TreeNode second)
{
if (first == null && second == null) {
return true;
}
// 如果其中一棵树为空，则不同
else if (first == null || second == null) {
return false;
}
// 如果两颗谁都不为空，则判断左右子树是否相同
if (first != null && second != null) {
if (first.val != second.val)
return false;
else
return isSameTree(first.left, second.left) && isSameTree(first.right, second.right);
}
return false;
}
}
发表于 2019-03-29 16:28:04
回复(0)
更多回答
class Solution
{
bool isSymmetrical(TreeNode *p_root1, TreeNode *p_root2)
{
if (p_root1 == nullptr && p_root2 == nullptr) // 对称的两个节点为空
return true;
else if (p_root1 == nullptr || p_root2 == nullptr) // 其中一个节点不为空
return false;
if (p_root1->val != p_root2->val) // 对称位置的值不相等
return false;
// 递归检查对称的位置：p1的左孩子和p2的右孩子，p1的右孩子p2的左孩子
return isSymmetrical(p_root1->left, p_root2->right) && isSymmetrical(p_root1->right, p_root2->left);
}
public:
bool isSymmetrical(TreeNode *pRoot)
{
return isSymmetrical(pRoot, pRoot);
}
};
发表于 2017-08-20 22:38:43
回复(0)
public class Solution {
boolean a=true;
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot==null)return a;
cal(pRoot.left,pRoot.right);
return a;
}
void cal(TreeNode b,TreeNode c){
if(b==null&&c==null){return;}
if(b!=null&&c==null||b==null&&c!=null){a=false;return;}
cal(b.left,c.right);
if(b.val!=c.val){a=false;return;}
cal(b.right,c.left);
return;
}
}
对称树的话除了跟节点随以外只需将其左右子树镜像对称，进行反方向遍历，如若有不等就返回false即可。
发表于 2016-07-15 15:57:57
回复(0)
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == NULL) return true;
return helper(pRoot->left,pRoot->right);
}
bool helper(TreeNode* l ,TreeNode* r){
if(l == NULL && r == NULL) return true;
if(l == NULL || r == NULL) return false;
return l->val == r->val && helper(l->left,r->right) && helper(l->right , r->left);
}
};
发表于 2015-08-20 12:34:43
回复(0)
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
stack<TreeNode*> s1,s2;
TreeNode *p1,*p2;
p1=p2=pRoot;
while((!s1.empty()&&!s2.empty())||(p1!=NULL&&p2!=NULL)){
while(p1!=NULL&&p2!=NULL){
s1.push(p1);
s2.push(p2);
p1=p1->left;
p2=p2->right;
}
p1=s1.top();
s1.pop();
p2=s2.top();
s2.pop();
if(p1->val!=p2->val)
return false;
p1=p1->right;
p2=p2->left;
}
if(!s1.empty()||!s2.empty())
return false;
if(p1!=NULL||p2!=NULL)
return false;
return true;
}
};
发表于 2017-06-01 11:16:19
回复(1)
/*
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 frontOrBack(pRoot,pRoot);
}
public static boolean frontOrBack(TreeNode pRoot1,TreeNode pRoot2){
if(pRoot1==null && pRoot2==null){
return true;
}
if(pRoot1==null || pRoot2==null){
return false;
}
if(pRoot1.val!=pRoot2.val){
return false;
}
return frontOrBack(pRoot1.right,pRoot2.left) && frontOrBack(pRoot1.left,pRoot2.right);
}
}
发表于 2018-05-30 10:57:31
回复(0)
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null)
return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
//比较左右子树对应节点是否相同
private boolean isSymmetrical(TreeNode pRoot1, TreeNode pRoot2) {
if (pRoot1 == null && pRoot2 == null)
return true;
if (pRoot1 == null || pRoot2 == null)
return false;
if (pRoot1.val != pRoot2.val)
return false;
return isSymmetrical(pRoot1.left, pRoot2.right) && isSymmetrical(pRoot1.right, pRoot2.left);
}
发表于 2017-06-09 11:21:16
回复(0)
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == NULL) return true;
return helper(pRoot->left, pRoot->right);
}
private:
bool helper(TreeNode* node1, TreeNode* node2){
if(node1==NULL && node2==NULL)
return true;
else if(node1!=NULL && node2!=NULL)
return (node1->val==node2->val) && helper(node1->left, node2->right)
&& helper(node1->right, node2->left);
else return false;
}
};
发表于 2017-06-04 15:46:41
回复(0)
class isSymmetricalTree
{
public:
bool isSymmetricalCore(TreeNode* pRoot,TreeNode* spRoot) //递归方法判断左右节点是否满足对称性
{
if(pRoot==nullptr && spRoot==nullptr) return true;
if(pRoot!=nullptr && spRoot!=nullptr && pRoot->val==spRoot->val) //树节点值相等
//递归，左右节点全满足对称性
return isSymmetricalCore(pRoot->left,spRoot->right) && isSymmetricalCore(pRoot->right,spRoot->left);
else
return false;
}
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot==nullptr) return true;
TreeNode* spRoot=pRoot;
return isSymmetricalCore(pRoot,spRoot);
}
};
发表于 2017-05-25 09:49:00
回复(0)
【java代码】满屏递归，无法挖掘这一题的价值。接下来提供递归的一个方法和非递归的2个方法参考。
//===================递归算法=============================//
1.只要pRoot.left和pRoot.right是否对称即可
2.左右节点的值相等且对称子树left.left， right.right ;left.rigth,right.left也对称
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot == null) return true;
return isSymmetrical(pRoot.left, pRoot.right);
}
private boolean isSymmetrical(TreeNode left, TreeNode right) {
if(left == null && right == null) return true;
if(left == null || right == null) return false;
return left.val == right.val //为镜像的条件：左右节点值相等
&& isSymmetrical(left.left, right.right) //2.对称的子树也是镜像
&& isSymmetrical(left.right, right.left);
}
//===================非递归算法，利用DFS和BFS=============================///*
* DFS使用stack来保存成对的节点
* 1.出栈的时候也是成对成对的 ，
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
* 2.确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left*/
boolean isSymmetricalDFS(TreeNode pRoot)
{
if(pRoot == null) return true;
Stack<TreeNode> s = new Stack<>();
s.push(pRoot.left);
s.push(pRoot.right);
while(!s.empty()) {
TreeNode right = s.pop();//成对取出
TreeNode left = s.pop();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
//成对插入
s.push(left.left);
s.push(right.right);
s.push(left.right);
s.push(right.left);
}
return true;
}
/** BFS使用Queue来保存成对的节点，代码和上面极其相似
* 1.出队的时候也是成对成对的
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
*/
boolean isSymmetricalBFS(TreeNode pRoot)
{
if(pRoot == null) return true;
Queue<TreeNode> s = new LinkedList<>();
s.offer(pRoot.left);
s.offer(pRoot.right);
while(!s.isEmpty()) {
TreeNode left= s.poll();//成对取出
TreeNode right= s.poll();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
//成对插入
s.offer(left.left);
s.offer(right.right);
s.offer(left.right);
s.offer(right.left);
}
return true;
}
编辑于 2019-07-26 12:47:19
回复(65)
#Python 版
#思路： 同时进行中左右 和中右左的遍历，并在遍历的时候比较节点
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSymmetrical(self, pRoot):
if pRoot is None:
return True
return self.isSymmetricalCore(pRoot,pRoot)
def isSymmetricalCore(self, pRoot, pRoot1):
if pRoot is None and pRoot1 is None:
return True
if pRoot is None or pRoot1 is None:
return False
if pRoot.val != pRoot1.val :
return False
return self.isSymmetricalCore(pRoot.left,pRoot1.right) and self.isSymmetricalCore(pRoot.right,pRoot1.left)
发表于 2016-12-08 22:40:26
回复(0)
public class Solution {
boolean isSymmetrical(TreeNode pRoot){
if(pRoot==null)
return true;
return isMirror(pRoot.left,pRoot.right);
}
public boolean isMirror(TreeNode left,TreeNode right){
if(left==null&&right==null)
return true;
if((left==null&&right!=null)
||(right==null&&left!=null)
||(left.val!=right.val)
||!(isMirror(left.left,right.right))
||!(isMirror(right.left,left.right))
)
return false;
return true;
}
}
发表于 2016-04-17 22:23:15
回复(0)
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null){
return true;
}
return judge(pRoot,pRoot);
}
boolean judge(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 != null && root2 != null && root1.val == root2.val) {
return judge(root1.left, root2.right) && judge(root1.right, root2.left);
}
return false;
}
}
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null){
return true;
}
return judge(pRoot,pRoot);
}
boolean judge(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 != null && root2 != null && root1.val == root2.val) {
return judge(root1.left, root2.right) && judge(root1.right, root2.left);
}
return false;
}
}
发表于 2022-05-27 13:18:49
回复(1)
递归判空判值完事
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot==null)return true;
return isSymmetrical(pRoot.left,pRoot.right);
}
boolean isSymmetrical(TreeNode p,TreeNode q) {
if(p==null && q==null)
return true;
if(p==null || q==null)
return false;
if(p.val != q.val)
return false;
return isSymmetrical(p.left,q.right) && isSymmetrical(p.right,q.left);
}
发表于 2022-03-12 15:27:02
回复(0)
方法1：拆成左右子树两个参数，用新函数递归
class Solution: '''法1：递归但不构造虚拟结点，改成多参数递归即可''' def isSym(self, p_left, p_right): if not p_left and not p_right: return True if not p_left&nbs***bsp;not p_right: return False if p_left.val != p_right.val: return False return self.isSym(p_left.left, p_right.right) and self.isSym(p_left.right, p_right.left) def isSymmetrical(self , pRoot: TreeNode) -> bool: return True if not pRoot else self.isSym(pRoot.left, pRoot.right)方法2：构造对称轴虚拟结点，用原函数递归
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool: '''法2：构造对称轴结点递归''' if not pRoot: return True if not pRoot.left and not pRoot.right: return True if not pRoot.left or not pRoot.right: return False if pRoot.left.val != pRoot.right.val: return False virtual_node_1, virtual_node_2 = TreeNode(0), TreeNode(0) virtual_node_1.left, virtual_node_1.right = pRoot.left.left, pRoot.right.right virtual_node_2.left, virtual_node_2.right = pRoot.left.right, pRoot.right.left return self.isSymmetrical(virtual_node_1) and self.isSymmetrical(virtual_node_2)方法3：用队列
class Solution: def isSymmetrical(self , pRoot: TreeNode) -> bool:) '''法1：队列''' if not pRoot: return True if not pRoot.left and not pRoot.right: return True if not pRoot.left&nbs***bsp;not pRoot.right: return False queue_l, queue_r = [pRoot.left], [pRoot.right] while queue_l != [] and queue_r != []: if queue_l[0].val != queue_r[0].val: return False l_pop, r_pop = queue_l.pop(0), queue_r.pop(0) if l_pop.left: if not r_pop.right: return False queue_l.append(l_pop.left) queue_r.append(r_pop.right) if l_pop.right: if not r_pop.left: return False queue_l.append(l_pop.right) queue_r.append(r_pop.left) return queue_l == [] and queue_r == []
发表于 2022-02-27 20:06:40
回复(0)
两个栈分别对两边进行判断，易于理解
import java.util.Stack;
/*
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) {
if(pRoot == null) return true;
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
TreeNode t1 = pRoot;
TreeNode t2 = pRoot;
while((t1!=null && t2 != null) ||(!s1.isEmpty() && !s2.isEmpty())){
while(t1!=null){
s1.push(t1);
t1 = t1.left;
}
while(t2!=null){
s2.push(t2);
t2 = t2.right;
}
TreeNode temp1 = s1.pop();
TreeNode temp2 = s2.pop();
if(temp1.val!=temp2.val)
return false;
t1 = temp1.right;
t2 = temp2.left;
}
if(!s1.isEmpty() || !s2.isEmpty()){
return false;
}
return true;
}
}
发表于 2022-01-06 10:11:00
回复(0)
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
// 空树也是对称的
if(pRoot == null)
return true;
return helper(pRoot.left, pRoot.right);
}
private boolean helper(TreeNode pRootL, TreeNode pRootR){
// 一直对比到最下面一层，还没有返回说明是对称的二叉树
if(pRootL == null && pRootR == null)
return true;
// 如果对比的过程中出现一边为空，另一边不为空的情况，说明不是对称的二叉树
else if(pRootL == null || pRootR == null)
return false;
// 否则向下去对比：pRootL和pRootR所指向的数值必须相同，同时，
// pRootL和pRootR向下走的时候，需要往相反的方向走
else return pRootL.val == pRootR.val &&
helper(pRootL.left, pRootR.right) && helper(pRootL.right, pRootR.left);
}
}
发表于 2021-11-14 10:25:04
回复(0)
我好像写代码总是这样，没有想到很好的办法，大多数情况都是穷举，而且有时候还过不了，需要爆出来的测试用例，一点一点的加上许多if。
你能想到还有这样的测试用例吗？
{5,5,5,5,#,#,5,5,#,5}
期望输出:false
{5,5,5,5,#,#,5,5,#,#,5}
期望输出:true
发表于 2021-09-16 17:06:35
回复(0)
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot == nullptr)
return true;
else
return isSymmetrical(pRoot -> left, pRoot -> right);
}
bool isSymmetrical(TreeNode* left, TreeNode* right)
{
if(left == nullptr && right == nullptr)
{
return true;
}
if(left == nullptr || right == nullptr || left -> val != right -> val)
{
return false;
}
return isSymmetrical(left -> left, right -> right) && isSymmetrical(left -> right, right -> left);
}
};
发表于 2021-08-30 22:37:44
回复(0)
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot == null) {
return true;
}
return check(pRoot.left, pRoot.right);
}
public boolean check(TreeNode L, TreeNode R) {
if(L == null && R == null) {
return true;
}
if(L == null || R == null) {
return false;
}
if(L.val != R.val) {
return false;
}
return check(L.left, R.right) && check(L.right, R.left);
}
}
发表于 2021-08-06 20:38:05
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-21 16:04:31 -
2023-02-13 22:11:16 -
2022-10-16 16:18:27
-
2022-09-16 21:04:24 -
2022-09-16 18:19:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同 * 左子树的右子树和右子树的左子树相同即可，采用递归 * 非递归也可，采用栈或队列存取各级子树根节点 */ public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null){ return true; } return comRoot(pRoot.left, pRoot.right); } private boolean comRoot(TreeNode left, TreeNode right) { // TODO Auto-generated method stub if(left == null) return right==null; if(right == null) return false; if(left.val != right.val) return false; return comRoot(left.right, right.left) && comRoot(left.left, right.right); } }