QQiing 普通 2023年9月24日上午12:23

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

};
时间复杂度：O(n)，空间复杂度：O(n)。

0 赞同 0 条回复

谁仁普通 2023年9月11日下午5:33

bool isSymmetric(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> q1, q2;
q1.push(root->left);
q2.push(root->right);
while (!q1.empty() && !q2.empty()) {
auto p1 = q1.front();
auto p2 = q2.front();
q1.pop();
q2.pop();
if (!p1 && !p2) continue;
if (!p1 || !p2 || p1->val != p2->val) return false;
q1.push(p1->left);
q1.push(p1->right);
q2.push(p2->right);
q2.push(p2->left);
}
return true;
}//时间复杂度O（n），空间复杂度O（n）

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年9月4日下午11:11

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return true

    q = queue()
    q.put(root.left)
    q.put(root.right)
    while not q.empty():
        left = q.get()
        right = q.get()
        if not left and not right:
            continue
        if not left or not right or left.val != right.val:
            return False
        q.put(left.left)
        q.put(right.right)
        q.put(left.right)
        q.put(right.left)
    return True

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

0 赞同 0 条回复

羊毛同学普通 2023年9月3日下午10:35

打卡

/**
 * 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 == NULL)
            return true;
        bool is_ = isjingxiang(root->left, root->right);
        return is_;
    }

    //判断left和right是否是镜像的
    bool isjingxiang(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;

        bool f1 = isjingxiang(left->left,right->right);
        bool f2 = isjingxiang(left->right,right->left);
        return f1 && f2;
    }
};

0 赞同 0 条回复

Miracle· 普通 2023年9月3日下午10:14

// // 递归,分别判断两个对称节点是否相同
// bool check(TreeNode left, TreeNode *right) {
// if (!left && !right) return true;
// if (!left || !right) return false;
// // 判断左右节点的值是否相同, 并且递归左子树的左孩子节点和右子树的右孩子节点判断,以及左子树的右孩子节点和右子树的左孩子节点
// return left->val right->val && check(left->left, right->right) && check(left->right, right->left);
// }
// bool isSymmetric(TreeNode root) {
// return check(root->left, root->right);
// }

// 迭代,使用队列来存节点
bool check(TreeNode *left, TreeNode *right) {
    queue <TreeNode*> q;
    q.push(left);
    q.push(right);
    while (!q.empty()) {
        left = q.front(); q.pop();
        right = q.front(); q.pop();
        if (!left && !right) continue;
        if ((!left || !right) || (left->val != right->val)) return false;
        q.push(left->left);
        q.push(right->right);

        q.push(left->right);
        q.push(right->left);
    }
    return true;
}
bool isSymmetric(TreeNode* root) {
    return check(root, root);
}

0 赞同 0 条回复

黎明之前普通 2023年9月3日下午6:07

//使用递归实现对称
//先进行头节点的判断判读后直接将其分成左右两个节点
//如果左右节点中的其中一个为空则为错误如果全为空则为真如果左右节点的不等为空
//如果左右节点的值相同则进行左右节点之后的左右判定递归遍历所有节点判定

class Solution{
public:
bool isSymmertic(Treenode *root)
{
if(root NULL||root.rightNULL root.leftNULL)
return root;
return f(root->left,root->right);
}
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);
}
};

0 赞同 0 条回复

Marc 普通 2023年9月2日下午7:52

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def Sysmetirc(root1, root2):
            if not root1 and not root2:
                return True
            if not root1 or not root2 or root1.val != root2.val:
                return False 
            return Sysmetirc(root1.left, root2.right) and Sysmetirc(root1.right, root2.left)

        if not root:
            return True  
        return Sysmetirc(root, root)

复杂度O(n)

0 赞同 0 条回复

sincere 普通 2023年8月26日上午12:13

思路：递归判断对称，递归等价条件注意 left.left - right.right 和 left.right - right.left 对比，本层级就是判断空的情况以及值的情况
复杂度：时间复杂度O(n)，空间复杂度O(logn)

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

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

    public Boolean symmetric(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;// 都不为空 但是值不相等肯定不对称
        }
        // left.left 和 right.right 对比; left.right 和 right.left 对比
        return symmetric(left.left, right.right) && symmetric(left.right, right.left);
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月24日下午11:44

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

/**
 * 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 check(TreeNode* p, TreeNode* q){
        if(!p&&!q) return true;
        if(!p||!q) return false;
        return p->val==q->val && check(p->left, q->right) && check(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL){
            return true;
        }else{
            return check(root->left, root->right);
        }
    }
};

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月21日下午11:16

时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(rootNULL) return true;
if(root->leftNULL&&root->rightNULL) return true;
return dfs(root->left, root->right);
}
bool dfs(TreeNode* a, TreeNode* b){
if(aNULL&&bNULL) return true;
if(aNULL||bNULL) return false;
return (a->valb->val)&&(dfs(a->left,b->right)&&(dfs(a->right,b->left)));
}
};

0 赞同 0 条回复

Sheng 永久会员 2023年8月21日下午5:14

自己用对比原来的树和镜像树是否相等的方法。
将答案的方法自己写了一遍

    //对称的二叉树
    //如果一棵二叉树和他的镜像一样，那么他是对称的
    //思路：找到他的镜像，看看两棵树是否一样
    //二叉树的镜像
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;

        TreeNode tmp;
        tmp = mirrorTree(root.left);
        root.left = mirrorTree(root.right);
        root.right = tmp;

        return root;
    }
    public boolean isSame(TreeNode root, TreeNode mirror) {
        if(root == null && mirror == null) return true;
        if(root == null || mirror == null) return false;
        return (root.val == mirror.val) && isSame(root.left, mirror.left) && isSame(root.right, mirror.right);
    }
    public boolean isSymmetric(TreeNode root) {
        TreeNode mirror = mirrorTree(root);
        return isSame(root, mirror);
    }
    //思路：对称位置的树节点是否相等
    public boolean isSame(TreeNode A, TreeNode B) {
        if(A == null && B == null) return true;
        if(A == null || B == null) return false;
        return (A.val == B.val) && isSame(A.left, B.right) && isSame(A.right, B.left);
    }
    public boolean isSymmetric(TreeNode root) {
        if(root == null || (root.left == null || root.right == null) return false;
        return isSame(root.left, root.right);
    }

0 赞同 0 条回复

木木普通 2023年8月21日下午3:40

時間複雜度: O(n) 空間複雜度: O(n)
需判斷左右子樹是否為空 , 若是一個空一個有值則可以提前返回false
若是都有值則繼續判斷左右節點值是否相同…


class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root, root);
    }

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

0 赞同 0 条回复

辰北、普通 2023年8月21日上午11:17

//root的左右支一起走，判断是否相等，递归输出，on，on时间空间

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

0 赞同 0 条回复

逸兴遄飞普通 2023年8月21日上午10:40

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

class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 树为空也是一种对称
        if(root == null) return true;
        // 对树的左右子树进行判断
        return check(root.left, root.right);
    }

    // 这里使用u和v双指针遍历，并且同时向相反的位置移动
    public boolean check(TreeNode u, TreeNode v) {
        // 前序相同情况下，同时遍历到null，对称
        if(u == null && v == null) {
            return true;
        }
        // 只有其中一个为null，或者两指针不相同的话，均不对称
        if((u == null || v == null) || (u.val != v.val)) {
            return false;
        }
        // 进行递归操作
        return check(u.left, v.right) && check(u.right, v.left);
    }
}

0 赞同 0 条回复

小肸永久会员 2023年8月20日下午9:40

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root, root);
    }
    //left、right都从root节点出发
    //left指向root的左子树中当前需要对比的节点
    //right指向root的右子树中当前需要对比的节点
    private boolean dfs(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        return dfs(left.right, right.left) && dfs(left.left, right.right) && left.val == right.val;
    }
}

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月19日下午3:50

“`python

class Solution:
def mirrorTree(self,l:TreeNode,r:TreeNode) -> bool:
if not l and not r: return True
if not l or not r or l.val != r.val: return False

    return self.mirrorTree(l.right,r.left) and self.mirrorTree(l.left, r.right)


def isSymmetric(self, root: TreeNode) -> bool:
    return self.mirrorTree(root.left,root.right) if root else True

    # #迭代方法，用双端队列左入左子树，右入右子树，层次入，然后比较节点。
    # if root is None: return True

    # d = deque()
    # d.appendleft(root.left)
    # d.append(root.right)

    # while d:#循环直接while d
    #     left_node = d.popleft()
    #     right_node = d.pop()

    #     if left_node is None and right_node is None:
    #         continue

    #     if left_node is None or right_node is None:
    #         return False

    #     if left_node.val != right_node.val:
    #         return False

    #     d.appendleft(left_node.right)
    #     d.appendleft(left_node.left)
    #     d.append(right_node.left)
    #     d.append(right_node.right)

    # return True

“`python

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月19日下午1:54

递归判断镜像

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

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

    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 条回复

c 普通 2023年8月19日下午1:06

递归判断

/**
 * 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(root==null){
            return true;
        }
        return dfs(root.left,root.right);
    }
    public boolean dfs(TreeNode n1,TreeNode n2){
        if(n1==null && n2==null){
            return true;
        }
        if(n1==null || n2==null || n1.val!=n2.val){
            return false;
        }
        return dfs(n1.left,n2.right)&&dfs(n1.right,n2.left);
    }
}

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月18日下午10:56

打卡

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }
    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);
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月18日下午10:32

1、递归

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

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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月18日下午7:25

 // 每次判断两个节点，再将这两个节点的左右节点进行判断
 // 时间O(n), 空间O(log n)
class Solution {
public:
    bool Symmetric(TreeNode* left,TreeNode* right)
    {
        if(!left&&!right) return true;
        if(!left||!right) return false;
        if(left->val!=right->val) return false;

        return Symmetric(left->right,right->left) && Symmetric(left->left,right->right);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return Symmetric(root->left,root->right);
    }
};
// 层次遍历的方式，判断
 // 时间O(n),空间O(log n)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*>q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty())
        {
            TreeNode* u = q.front();q.pop();
            TreeNode* v = q.front();q.pop();
            if(!u&&!v) continue;
            if((!u||!v)||(u->val!=v->val)) return false;
            q.push(u->left);
            q.push(v->right);
            q.push(u->right);
            q.push(v->left);
        }
        return true;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月18日下午5:51

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

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        std::queue<TreeNode*> nodes;
        nodes.push(root);
        nodes.push(root);

        TreeNode* n1 { nullptr };
        TreeNode* n2 { nullptr };
        while (!nodes.empty()) {
            n1 = nodes.front();
            nodes.pop();
            n2 = nodes.front();
            nodes.pop();

            if (!n1 && !n2) { // 两个都是空
                continue;
            }
            // 其中一个是空另一个不是空，或者两个值不相等，一定不是镜像
            if ((!n1 || !n2) || (n1->val != n2->val)) {
                return false;
            }

            nodes.push(n1->left);
            nodes.push(n2->right);

            nodes.push(n2->left);
            nodes.push(n1->right);
        }
        return true;
    }
};

0 赞同 0 条回复

帝心引力永久会员 2023年8月18日下午2:51

时间o(n), 空间o(n)
class Solution {
public:
    bool isSame(TreeNode* rootA, TreeNode* rootB){
        if(rootA == NULL && rootB == NULL){
            return true;
        }
        if(rootA == NULL || rootB == NULL){
            return false;
        }
        return rootA->val == rootB->val && isSame(rootA->right, rootB->left) && isSame(rootA->left, rootB->right);
    }
    bool isSymmetric(TreeNode* root) {
        return isSame(root, root);
    }
};

0 赞同 0 条回复

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

共以下 23 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题取消回复

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

共以下 23 个回答

Definition for a binary tree node.

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

# 回答此问题 取消回复

# 回答此问题取消回复