九号球普通 2023年11月14日下午9:07

“`java
关键在于要判断好最左和最右和内左内右对称
class Solution {
public boolean checkSymmetricTree(TreeNode root) {
if (root == null) {
return true;
}
return check(root.left, root.right);
}
public boolean check(TreeNode p, TreeNode q) {
Queue queue = new LinkedList<>();
queue.offer(p);
queue.offer(q);
while (!queue.isEmpty()) {
TreeNode m = queue.poll();
TreeNode n = queue.poll();
if (m == null && n == null) {
continue;
}
if (m == null || n == null || m.val != n.val) {
return false;
}
queue.offer(m.right);
queue.offer(n.left);
queue.offer(m.left);
queue.offer(n.right);
}
return true;
}
}

0 赞同 0 条回复

大大普通 2023年11月14日下午9:06

c++

 //镜像右子树 判断左右子树是否一样
class Solution {
public:
    bool Issame(TreeNode* r1,TreeNode* r2){
      if(r1==NULL&&r2==NULL)return true;
      if(r1&&r2){
        if(r1->val==r2->val){
          return Issame(r1->left,r2->left)&&Issame(r1->right,r2->right);
        }
        else return false;
      }return false;

    }
    TreeNode* Swap(TreeNode* root){
      if(root==NULL)return root;
      TreeNode* tp=root->left;
      root->left=Swap(root->right);
      root->right=Swap(tp);
      return root;
    }
    bool checkSymmetricTree(TreeNode* root) {
     if(root==NULL)return true;
     root->right=Swap(root->right);
     return Issame(root->left,root->right);
    }
};

 //看成两棵树
class Solution {
public:
bool check(TreeNode* a,TreeNode* b){
  if(!a&&!b)return true;
  if((!a||!b)||(a->val!=b->val))return false;
  return check(a->left,b->right)&&check(a->right,b->left);
}
    bool checkSymmetricTree(TreeNode* root) {
     if(root==NULL)return true;
     return check(root->left,root->right);
    }
};


//看成两个树 类似于层序遍历 同步的层序遍历
class Solution {
public:
    bool checkSymmetricTree(TreeNode* root) {
    if(root==NULL)return true;
    queue  q;
    q.push(root->left);
    q.push(root->right);
      TreeNode* h1=NULL;TreeNode* h2=NULL;
      while(!q.empty()){
          h1=q.front();
          q.pop();
         h2=q.front();
          q.pop();
          if(!h1&&!h2);
        else if((!h1||!h2)||(h1->val!=h2->val)) return false;
        else{
            q.push(h1->left);
            q.push(h2->right);
            q.push(h1->right);
            q.push(h2->left);     
        }        
    } return true;
    }
};

0 赞同 0 条回复

往远处看普通 2023年9月8日下午11:23

Problem: 剑指 Offer 28. 对称的二叉树

[TOC]

思路

通过递归方式将两边子树都往下递归，知道递归到两边的叶子节点，执行到这一步 A==NULL && B == NULL 结束循环返回 true 如果不是对称二叉树则返回false

解题方法

两个递归调用

复杂度

o(n)
– 时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:
> 树的高度

Code

“`C++ []

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode root) {
if(root nullptr) return true;
if(root->left nullptr && root->right nullptr) return true;
return f(root->left,root->right);

public:
bool f(TreeNode* A,TreeNode* B){
if(Anullptr && Bnullptr) return true;
if(A nullptr || B nullptr) return false;
if(A->val != B->val) return false;

    return f(A->left,B->right) && f(A->right,B->left);
}

};

“`

0 赞同 0 条回复

招舟子普通 2023年8月25日下午6:32

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if(rootnull){
return true;
}
return same(root.right,root.left);
}
public boolean same(TreeNode a,TreeNode b){
if(anull&&bnull){return true;}
if(anull||bnull){return false;}
if(a.val!=b.val){return false;}
return same(a.right,b.left)&&same(a.left,b.right);
}
}
对称二叉树递归比较左节点和右节点，。

0 赞同 0 条回复

淡色花樱普通 2023年7月18日下午4:14

“`java
public boolean isSymmetric (TreeNode root){
return root ==null?true:isSymmetric(root.left,root.right);
}
public boolean isSymmetric(TreeNode left,TreeNode right){
//一个节点，左右都为空，那么就是对称
if(left == null &&right == null)||(right.val!= left.val)){
return false;
}
//镜像对比
return isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left);
}
时间复杂度0(n) 空间复杂度0(n)

0 赞同 0 条回复

cute. 普通 2023年7月12日下午2:18

思路：判断左右子树是否是否互相为镜像二叉树

var isSymmetric = function(root) {
    if(root === null || (root.left === null && root.right === null))
        return true;
    return f(root.left, root.right);
};
var f = function(a, b) {
    if( a === null && b === null) {
        return true;
    }
    if( a === null || b === null) {
        return false;
    }
    if(a.val !== b.val) {
        return false;
    }
    return f(a.left, b.right) && f(a.right, b.left);
}

0 赞同 0 条回复

jhfuture 普通 2023年7月10日上午11:14

class Solution {
    public boolean isSymmetric(TreeNode root) {
                if(root==null||root.left==null&&root.right==null) return true;
               return f(root.left,root.right);
    }

    public boolean f(TreeNode A,TreeNode B){
        if(A==null&&B==null) return true;
        if(A==null||B==null) return false;
        if(A.val!=B.val) {
            return false;
        }
        return f(A.left,B.right)&&f(A.right,B.left);
    }
}

思路：这里有一个思考为什么在 f函数中 val相等时不返回 true，因为当递归到最后一个空结点时，其值就为true，会一直向上传递

0 赞同 0 条回复

CV大神普通 2023年7月7日下午8:48

public boolean isSymmetric(TreeNode root) {
        return root == null ? true:isSymmetric(root.left,root.right);
    }

    public boolean isSymmetric(TreeNode left,TreeNode right){
        //一个节点，左右都为空，那么就是对称
        if(left == null && right == null) return true;
        //如果有一个不为空（能到这里，肯定不是都空），那么不是对称的；如果都不空，但是值不相等，也不是对称的
        if((left == null || right == null) || (right.val != left.val) ){
            return false;
        }
        //镜像对比
        return isSymmetric(left.left,right.right) && isSymmetric(left.right,right.left);
    }

时间复杂度O(n)，空间复杂度O（n）

0 赞同 0 条回复

BOZ 普通 2023年7月7日上午10:30

【思路】递归思路，根结点的左右子树应该互为镜像，左子树的左子树与右子树的右子树又互为镜像，以此类推完成递归。之前有考虑过用广度优先遍历的方法，但该方法需要使用栈/队列之类的辅助数据结构，因此空间复杂度会更高O(logn)。
【复杂度】时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    bool _isSymmetric(TreeNode* A, TreeNode* B) {
        if (A == NULL && B == NULL) return true;
        if (A == NULL || B == NULL || A->val != B->val) return false;
        return (_isSymmetric(A->left, B->right) && _isSymmetric(A->right, B->left));
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return _isSymmetric(root->left, root->right);
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月6日下午7:47

C++实现

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;

        return isSymmetric(root -> left, root -> right);


    }

    bool isSymmetric(TreeNode* left, TreeNode* right) {
        //1.第一个结束条件，左右节点都为空
        if(!left && !right) return true;

        //2.第二个结束条件，一个节点为空另一个不为空 或者两边数据不一致则返回false
        if(!left || !right || left -> val != right -> val) return false;

        //符合要求则判断下一层
        return isSymmetric(left -> left, right -> right) && isSymmetric(left -> right, right -> left);

    }
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月5日下午2:56

这段代码中，定义了一个 Solution 类，其中包含了一个 isSymmetric 函数，用于判断二叉树是否对称。函数接收一个二叉树的根节点作为参数，返回一个布尔值，表示二叉树是否对称。
在 isSymmetric 函数中，首先判断根节点是否为空。如果为空，则直接返回 True ，因为空树被认为是对称的。
如果根节点不为空，则调用 checkSymmetry 函数来判断左右子树是否对称。 checkSymmetry 函数接收左右子树的根节点作为参数，返回一个布尔值，表示左右子树是否对称。
在 checkSymmetry 函数中，有以下几种情况需要考虑：
– 如果左右子树的根节点都为空，说明当前节点是叶子节点，对称性成立，返回 True 。
– 如果左右子树的根节点只有一个为空，说明左右子树结构不对称，返回 False 。
– 如果左右子树的根节点的值不相等，说明左右子树的节点值不对称，返回 False 。
– 否则，递归地判断左子树的左节点和右子树的右节点是否对称，以及左子树的右节点和右子树的左节点是否对称。如果都对称，则返回 True ，否则返回 False 。
通过递归地判断二叉树的左右子树是否对称，从而判断整个二叉树是否对称。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        return self.check(root.left, root.right)

    def check(self, left: TreeNode, right: TreeNode) -> bool:
        if left is None and right is None:
            return True
        if left is None or right is None or left.val != right.val:
            return False
        return self.check(left.left, right.right) and self.check(left.right, right.left)

0 赞同 0 条回复

断舍离永久会员 2023年7月5日上午8:41

class Solution {
    public boolean isSymmetric(TreeNode root) {
       //特殊条件，空树默认返回true
        if(root == null){
            return true;
        }
        return f(root.left, root.right);
    }

    public boolean f(TreeNode A, TreeNode B){
        //递归终止条件1：2颗子树全为空，则为对称
        if(A == null && B == null){
            return true;
        }
        //递归终止条件2：有1颗子树为空，则肯定不对称
        if(A == null || B == null){
            return false;
        }

        //递归终止条件3：若2树节点不一致，则肯定不对称
        if(A.val != B.val){
            return false;
        }

        return f(A.left, B.right) && f(A.right, B.left);
    }
}

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午1:05

递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null)
            return true;
        return Symmrtric(root.left,root.right);
    }
    public boolean Symmrtric(TreeNode left,TreeNode right){
        if(left==null&&right==null)
            return true;
        if(left==null)
            return false;
        if(right==null)
            return false;
        if(left.val!=right.val)
            return false;
        return Symmrtric(left.left,right.right)&&Symmrtric(left.right,right.left);
    }
}

0 赞同 0 条回复

　　　　　　　　普通 2023年7月3日下午12:54

class Solution {
public: 
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)return root;
        TreeNode* l=mirrorTree(root->right);
        TreeNode* r=mirrorTree(root->left);
        root->left=l;
        root->right=r;
        return root;
    }
};

【时间O(n),空间O(1)】
递归

0 赞同 0 条回复

mpweixin用户普通 2023年7月3日上午10:35

java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        //判断根节点的左子树和右子树是否为镜像二叉树
        if(root == null || (root.left == null && root.right == null)) {
            return true;
        }

        return judgeMirrorTree(root.left, root.right);
    }

    public boolean judgeMirrorTree(TreeNode A, TreeNode B) {
        if(A == null && B == null) {
            return true;
        }

        if(A == null || B == null) {
            return false;
        }

        if(A.val != B.val) {
            return false;
        }

        return judgeMirrorTree(A.left, B.right) &&judgeMirrorTree(A.right, B.left);
    }
}

时间和空间复杂度都是O(N)

0 赞同 0 条回复

局外人普通 2023年7月3日上午10:26

思路：采用辅助函数，同时传入左右子树，以此查看是否对称
时间复杂度O(n) 空间复杂度O(n)

class Solution {
    public boolean check(TreeNode p ,TreeNode q){
        if(p==null && q==null)  return true;
        if(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, root);
    }
}

0 赞同 0 条回复

地平线真勇敢普通 2023年7月2日下午3:47

public boolean isSymmetric(TreeNode root) {
if(root null || (root.left null && root.right null)){
return true;
}
return f(root.left,root.right);
}
public boolean f(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 f(l.left,r.right)&&f(l.right,r.left);
}
时间复杂度：o(n)
空间复杂度：o(n)

0 赞同 0 条回复

mpweixin用户普通 2023年7月1日下午4:21

bool traversal(struct TreeNode* left, struct TreeNode* right) {
    if ((left && !right) || (!left && right)) {
        return false;
    } else if (!left && !right) {
        return true;
    } else if (left->val != right->val) {
        return false;
    }
    return traversal(left->left, right->right) && traversal(left->right, right->left);
}
bool isSymmetric(struct TreeNode* root) {
    if (!root) {
        return true;
    }
    return traversal(root->left, root->right);
}

时间复杂度为O(n)
空间复杂度为O(n)

0 赞同 0 条回复

花老爷普通 2023年6月30日上午9:58

递归
时间：O(n)
空间：O(n)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return reserve(root.left, root.right);
    }

    private boolean reserve(TreeNode l, TreeNode r) {
        if (l == null && r == null) {
            return true;
        } else if ((l != null && r == null) || (l == null && r != null) || l.val != r.val) {
            return false;
        }
        return reserve(l.left, r.right) && reserve(l.right, r.left);
    }
}

0 赞同 0 条回复

拾陆. 普通 2023年6月29日下午10:58

class Solution {
public:
    bool check(TreeNode* p, TreeNode* q){
        if(p== nullptr && q == nullptr) return true;
        if(p == nullptr || q == nullptr) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        return check(root->left, root->right) && check(root->right, root->left);
    }
};

可以

0 赞同 0 条回复

～普通 2023年6月29日上午10:06

class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(rootnullptr){
return true;
}
return isMirror(root->left, root->right);
}
bool isMirror(TreeNode* left, TreeNode* right){
if(leftnullptr&&rightnullptr){
return true;
}
if(leftnullptr||rightnullptr||left->val!=right->val){
return false;
}
return isMirror(left->left, right->right)&&isMirror(left->right, right->left);
}
};
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日上午6:23

时间复杂度O(n)
空间复杂度O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) {
            return true;
        }
        return checkSymmetric(root->left, root->right);
    }
    bool checkSymmetric(TreeNode* left, TreeNode* right) {
        if (!left && !right) {
            return true;
        } else if (left && right) {
            if (left->val != right->val) {
                return false;
            }
            return checkSymmetric(left->left, right->right) && checkSymmetric(left->right, right->left);
        } else {
            return false;
        }
    }
};

0 赞同 0 条回复

Bello~ 普通 2023年6月28日下午11:25

时间复杂度O(N)
空间复杂度O(N)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return recur(root.left, root.right);
    }

    private boolean recur(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月28日下午5:58

时间复杂度 O(N)
空间复杂度 O(N)

bool check(struct TreeNode* left, struct TreeNode* right){
    if(left == NULL && right == NULL){
        return true;
    }
    if(left == NULL || right == NULL){
        return false;
    }
    if(left->val != right->val){
        return false;
    }

    return check(left->left, right->right) && check(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root){
    if(root == NULL || (root->left == NULL && root->right == NULL)){
        return true;
    }
    return check(root->left,root->right);
}

0 赞同 0 条回复

江畅普通 2023年6月28日上午12:02

// 对称的二叉树
// 时间复杂度 O(N)
// 空间复杂度 O(N)
class Solution {
private:
    // check 左右子树是否对称
    bool check(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) {
            return true;
        }
        else if (left == nullptr || right == nullptr || left->val != right->val) {
            return false;
        }
        return check(left->left, right->right) && check(left->right, right->left);
    }

public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        return check(root->left, root->right);
    }
};

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月27日下午10:48

一开始不会，看完讲解会了
时间复杂度：O(N)
空间复杂度：O(N)

class Solution {

    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
    }

    // 1. 明确函数功能：输入 + 输出
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        // 2. 明确递归结束条件
        if(left == null && right == null) return true;
        if(left == null || right == null) return false;
        if(left.val != right.val) return false;
        // 3. 明确函数的等价关系式
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

0 赞同 0 条回复

小吕普通 2023年6月27日下午9:25

c++递归
bool compare(TreeNode* left,TreeNode* right)
{
if(leftNULL&&rightNULL)return true;
else if(leftNULL&&right!=NULL)return false;
else if(left!=NULL&&rightNULL)return false;
else if(left->val!=right->val)return false;
bool outside = compare(left->left,right->right);
bool inside = compare(left->right,right->left);
return outside&&inside;
}
bool isSymmetric(TreeNode* root) {
if(rootNULL)return true;
return compare(root->left,root->right);
}

0 赞同 0 条回复

屠龙手段普通 2023年6月26日下午8:40

递归
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    lst1 = []
    lst2 = []

    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        if not root.left and not root.right:
            return True
        return self.isMirror(root.left, root.right)

    def isMirror(self, left, right):
        if not left and not right:
            return True
        if (not left and right) or (left and not right):
            return False
        if left.val != right.val:
            return False
        return self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)

0 赞同 0 条回复

彦，，# 普通 2023年6月26日下午5:26

这个有点想复杂了都是O(n)

bool check(TreeNode *p,TreeNode *q)
    {
        if(!p && !q ) return true;
        if(!p || !q)  return false;
        return p->val == p->val && check(p->left, p->right) && check(p->right,p->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }

0 赞同 0 条回复

普通 2023年6月26日下午4:52

class Solution {
    boolean isSymmetric = true;
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return isSymmetric;
        forEachTree(root.left,root.right);
        return isSymmetric;
    }

    public void forEachTree(TreeNode l ,TreeNode r){
        if(l == null && r == null){
            return ;
        }
        if((l == null || r == null) || l.val != r.val){
            isSymmetric = false;
            return;
        }
        forEachTree(l.left,r.right);
        forEachTree(l.right,r.left);
    }
}

递归
判断两节点 l.left 和 r.right是否对称
判断两节点 l.right 和 r.left是否对称
不对称就改全局变量isSymmetric为false并退出

0 赞同 0 条回复

残月冷骄阳普通 2023年6月26日下午12:03

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
       return check(root,root);

    }
    public boolean check(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if(left==null || right==null){
            return false;
        }
        return left.val==right.val&&check(left.left,right.right)&&check(left.right,right.left);
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月26日上午12:20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

        def isSymmetricHelepr(left, right):
            if not left and not right:
                return True
            elif not left or not right:
                return False
            else:
                return left.val == right.val and isSymmetricHelepr(left.right, right.left) and isSymmetricHelepr(left.left, right.right)

        return isSymmetricHelepr(root.left, root.right)
        #使用helper

0 赞同 0 条回复

大鑫啊普通 2023年6月25日下午11:37

时空复杂度：O(n)
1、递归分析
2、新建方法f返回左右子树是否为镜像二叉树
3、f中判断如果两个结点A、B数值相同，继续递归判断A的左子树和B的右子树是否相等

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left == null && root.right == null))return true;
        return f(root.left,root.right);
    }
    public boolean f(TreeNode A,TreeNode B){
        if(A == null && B == null)return true;
        if(A == null || B == null)return false;
        if(A.val != B.val)return false;
        return f(A.left,B.right) && f(A.right,B.left);

    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年6月25日下午10:46

// 递归解法
 //时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root||(!root->left&&!root->right)) return true;
        return recur(root->left,root->right);
    }
    bool recur(TreeNode* left, TreeNode* right)
    {
        if(left==NULL&&right==NULL) return true;
        if(left==NULL||right==NULL) return false;
        if(left->val!=right->val) return false;

        return recur(left->left,right->right)&&recur(left->right,right->left);

    }
};

0 赞同 0 条回复

Jerry 普通 2023年6月25日下午10:13

 //递归
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return recur(root.left, root.right);
    }

    boolean recur(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null || left.val != right.val) return false;
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

伏月三十普通 2023年6月25日下午9:27

自己没想出来哇哇哇
时间复杂度O(n) 空间复杂度：树的高度

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null || (root.left==null && root.right==null)){
            return true;
        }
        return f(root.left,root.right);
    }

    //判断A和B是否互为镜像二叉树
    private boolean f(TreeNode A,TreeNode B){
        if(A==null && B==null){
            return true;
        }
        if(A==null || B==null){
            return false;
        }
        if(A.val!=B.val){
            return false;
        }
        return f(A.left,B.right) && f(A.right,B.left);
    }
}

0 赞同 0 条回复

硬核洋葱普通 2023年6月25日下午9:16

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        TreeNode*p1 = root, *p2 = root;
        return recur_isSymmetric(p1, p2, root);
    }

    bool recur_isSymmetric(TreeNode* p1, TreeNode* p2, TreeNode* root){
        if(!p1 && !p2)
            return true;
        if(!p1 || !p2)
            return false;

        bool ans = recur_isSymmetric(p1->left, p2->right, root);
        if(!ans)
            return false;
        if(p1->val != p2->val)
            return false;
        if(p1 == root)
            return true;
        return recur_isSymmetric(p1->right, p2->left, root);
    }
};

一个节点左根右深度遍历，一个节点右根左深度遍历，不断比较这两个节点即可
为了防止重复遍历，即整棵树的根节点左边和右边比较一次，右边和左边比较一次。当这两个点都遍历到根节点时，停止
时间复杂度O(n) 空间复杂度 O(h)

0 赞同 0 条回复

Dsjh 普通 2023年6月25日下午8:37

// c++ 实现
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root){
            return true;
        }
        return check(root->left,root->right);
    } 
    bool check(TreeNode* l,TreeNode* r){
        if(!l && !r){
            return true;
        }
        if(!l || !r || l->val != r->val){
            return false;
        }
        return check(l->left,r->right) && check(l->right,r->left);
    }
};

0 赞同 0 条回复

peach 普通 2023年6月25日下午8:18

思路

看左右子树是否镜像，然后继续递归即可

代码


 //递归解法 时间复杂度O(n) 空间复杂度O(logn)
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isMirror(root.left, root.right); //看左右子树是否互为镜像
    }
    private boolean isMirror(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 == null) return true;
        if(root1 == null || root2 == null) return false;
        if(root1.val != root2.val) return false;
        return isMirror(root1.left, root2.right) && isMirror(root1.right, root2.left); //递归
    }
}

0 赞同 1 条回复

peach 普通 @ peach 2023年6月25日下午8:19

无

登录以回复

mpweixin用户永久会员 2023年6月25日下午8:16

//时间O(n)，空间O(logn)
public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)){
            return true;
        }

        return isMirror(root.left,root.right);

    }

    boolean isMirror(TreeNode left,TreeNode right){
        //判断自己
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }

        //判断孩子
        return isMirror(left.left,right.right) && isMirror(left.right,right.left);
    }

0 赞同 0 条回复

怀瑾永久会员 2023年6月25日下午8:15

C++实现

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isSymmetric(TreeNode* root) {
    if (root == nullptr) return true;
    return isSymmetricCore(root->left, root->right);
}

bool isSymmetricCore(TreeNode* left, TreeNode* right) {
    if (left == nullptr && right == nullptr) return true;
    if (left == nullptr || right == nullptr || left->val != right->val) return false;
    return isSymmetricCore(left->left, right->right) && isSymmetricCore(left->right, right->left);
}

0 赞同 0 条回复

张开怀普通 2023年6月25日下午7:09

/**
 * struct TreeNode{
 *      int val;
 *      TreeNode* left;
 *      TreeNode* right;
 *      TreeNode(int x) : val(x), left(NULL), right(NULL){ }
 *  }
 */
class Solution{
public:
      bool isSymmetric(TreeNode* root){
             if(!root || (!root->left && !root->right)){
                   return true;
             }
             return f(root->left, root->right);
      }

      // 判断B是不是以A为根节点的子树
      bool f(TreeNode* A, TreeNode* B){
            if(!A && !B){
                  return true;
            }
            if(!A || !B){
                  return false;
            }
            if(A->val != B->val){
                  return false;
            }
            return f(A->left, B->right) && f(A->right, B->left);
      }
}

时间复杂度：O(n)
空间复杂度：树的高度

0 赞同 0 条回复

Vow the vow。普通 2023年6月25日下午6:59

时间复杂度和空间复杂度都是O(n)。

public boolean isSymmetric(TreeNode root) {
        if(root == null ) return true;
        return isSymmetric(root.left, root.right);
    }

    public boolean isSymmetric(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 == null) return true;
        if(node1 == null || node2 == null) return false;
        if(node1.val != node2.val) return false;
        return isSymmetric(node1.left, node2.right) && isSymmetric(node1.right, node2.left);
    }

0 赞同 0 条回复

Ming 普通 2023年6月25日下午3:26

复杂度O(n) O(height)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) {
            return true;
        }
        return f(root.left, root.right);
    }
    public boolean f(TreeNode A, TreeNode B) {
        if(A == null && B == null) {
            return true;
        }
        if(A == null || B == null) {
            return false;
        }
        if(A.val != B.val) {
            return false;
        }
        return f(A.left, B.right) && f(A.right, B.left);
    }
}

0 赞同 0 条回复

yxy 普通 2023年6月25日下午3:08

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* left, TreeNode* right)
    {
        bool out = true, in = true;
        if(!left&&right) return false;
        if(left&&!right) return false;
        if(!left&&!right) return true;
        if(left->val!=right->val) return false;
        out = isSymmetric(left->left, right->right);
        in = isSymmetric(left->right, right->left);
        return in&&out;
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return isSymmetric(root->left, root->right);
    }
};

复杂度O（n） O（n）

0 赞同 0 条回复

Yodl. 普通 2023年6月25日下午3:00

class Solution {
public:
    bool check(TreeNode* root,TreeNode* mirror_tree)
    {
        if(root==NULL&&mirror_tree==NULL)
        {
            return true;
        }
        if(root==NULL||mirror_tree==NULL)
        {
            return false;
        }
        if(root->val!=mirror_tree->val)
        {
            return false;
        }
        return check(root->left,mirror_tree->right)&&check(root->right,mirror_tree->left);
    }

    bool isSymmetric(TreeNode* root) {
        if(root==NULL)
        {
            return true;
        }
        return check(root->left,root->right);
    }
};
时间复杂度：O(n)
空间复杂度：树的高度

0 赞同 0 条回复

雨落圆荷普通 2023年6月25日下午1:58

class Solution {
public boolean isSymmetric(TreeNode root) {
if(root null || (root.left null && root.right null)){
return true;
}

    return f(root.left, root.right);
}
// 判断B是不是以A阶段为根节点的子树
public boolean f(TreeNode A, TreeNode B){
    if(A == null && B == null){
        return true;
    }

    if(A == null || B == null){
        return false;
    }

    if(A.val != B.val){
        return false;
    }

    return f(A.left, B.right) && f(A.right, B.left);
}

}
时间复杂度：O(n)
空间复杂度：树的高度

0 赞同 0 条回复

【二叉树专题】剑指 Offer 28. 对称的二叉树

共以下 47 个回答

思路

解题方法

复杂度

Code

复杂度

Code

思路

代码

# 回答此问题取消回复

【二叉树专题】剑指 Offer 28. 对称的二叉树

共以下 47 个回答

思路

解题方法

复杂度

Code

复杂度

Code

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复