【二叉树专题】剑指 Offer 28. 对称的二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

桎梏普通 2023年8月11日下午9:35

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

    public boolean compare(TreeNode left, TreeNode right) {
        if(left == null && right != null) {
            return false;
        }
        if(left != null && right == null) {
            return false;
        }
        if(left == null && right == null) {
            return true;
        }
        if(left.val != right.val) {
            return false;
        }
        //比较外侧
        boolean compareOutside = compare(left.left, right.right);
        //比较内侧
        boolean compareInside = compare(left.right, right.left);
        return compareOutside && compareInside;
    }
}

0 赞同 0 条回复

hi 普通 2023年8月6日上午10:42

变为判断左右子树是否为镜像

/**
 * 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;
        return dfs(root->left, root -> right); 
    }

    bool dfs(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 dfs(A -> left, B -> right) && dfs(A -> right, B -> left);
    }
};

0 赞同 0 条回复

今天没时间刷题普通 2023年7月31日下午10:35

时间On，空间Oheight
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return isSym(root->left, root->right);
    }

    bool isSym(TreeNode* left, TreeNode* right)
    {
        if(!left && !right) return true;
        if(left && !right) return false;
        if(!left && right) return false;

        return left->val == right->val 
                    && isSym(left->left, right->right)
                    && isSym(left->right, right->left);
    }
};

0 赞同 0 条回复

朱志刚普通 2023年7月20日下午6:19

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==NULL||(root->left==NULL&&root->right==NULL))return true;
        return dfs(root->left,root->right);

    }
       bool dfs(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 dfs(A->left,B->right)&&dfs(B->left,A->right);

    }
};

执行用时：
12 ms

0 赞同 0 条回复

小季同学普通 2023年7月19日下午9:29

对称二叉树

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSymmetric(root: TreeNode | null): boolean {
    // 边界判断
    if(!root || (root.left == null && root.left == null)) {
        return true
    }
    // 判断左右子树是否互为镜像
    return isSame(root.left, root.right)
};

function isSame(a: TreeNode, b: TreeNode) {
    // 考虑边界情况
    if(a==null && b==null) {
        return true
    }
    if(a==null || b==null) {
        return false
    }
    if(a.val != b.val) {
        return false
    }
    return isSame(a.left, b.right) && isSame(a.right, b.left)
}

0 赞同 0 条回复

Terence💧 普通 2023年7月18日下午10:17

对称二叉树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return recur(root.Left, root.Right)
}

func recur(left *TreeNode, right *TreeNode) bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil || right == nil || left.Val != right.Val{
        return false
    }
    return recur(left.Left, right.Right) && recur(left.Right, right.Left)
}

0 赞同 0 条回复

doordie. 普通 2023年7月18日下午3:46

递归

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

    private boolean recur(TreeNode L, TreeNode R) {
        if (L == null && R == null){
            return true;
        }
        // 节点值不相等、只有一个为空  就不对称
        if(L == null || R == null || L.val != R.val){
            return false;
        }

        return recur(L.left, R.right) && recur(L.right, R.left);

    }
}

0 赞同 0 条回复

枫梓。普通 2023年7月18日上午11:46

class Solution {
public:
    bool check(TreeNode* lt, TreeNode* rt) {
        queue<TreeNode*> q;
        q.push(lt);
        q.push(rt);
        while(!q.empty()){
            lt = q.front();
            q.pop();
            rt = q.front();
            q.pop();
            if(!lt && !rt)
                continue;
            if((!lt || !rt) || lt->val != rt->val)
                return false;
            q.push(lt->left);
            q.push(rt->right);
            q.push(lt->right);
            q.push(rt->left);
        }
        return true;
    }
    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

层序遍历来判断对称，时间复杂度O(n), 空间复杂度队列中最多有一半结点，故为O(n)

0 赞同 0 条回复

Mby 普通 2023年7月17日下午5:53

/**
 * 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 || (root.left == null && root.right == null)){
            return true;//符合就 是对称二叉树
        }

        return f(root.left, root.right);//否则 定义f函数    判断根节点的左右子树是否为镜像，是镜像就为对称二叉树

    }

    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年7月17日下午5:48

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){   //if不能调换！先检查 A 和 B 是否至少有一个为空，然后再检查值是否相等，那么在检查值相等之前，已经判断了非空子树不对称的情况，导致无法判断对称性。
                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年7月16日下午10:51

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        // 判断左右子树是否互为镜像
        return isMirror(root.left,root.right);
    }

    public boolean isMirror(TreeNode left, TreeNode right){
        if(left==null&&right==null) return true;
        // 只有一方为null，不为镜像
        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);
    }
}

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

0 赞同 0 条回复

艺普通 2023年7月16日下午10:07

“`c++
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
bool dfs(TreeNode *A,TreeNode *B)
{
if(A==NULL&&B==NULL) return true;
if(A==NULL||B==NULL) return false;
return A->val==B->val&&dfs(A->left,B->right)&&dfs(A->right,B->left);
}
bool isSymmetric(TreeNode* root) {
if(root==NULL) return true;
return dfs(root->left,root->right);
}
};
“`

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月16日下午9:27

代码

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 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 f(left.left, right.right)&&f(left.right, right.left);
    }

}

0 赞同 0 条回复

神经蛙普通 2023年7月16日下午2:48

/**
    时间复杂度O(n)
    空间复杂度O(n)
    递归判断左右子树是否相等
    前序遍历
*/
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return recur(root.left, root.right);
    }

    public boolean recur (TreeNode left, TreeNode right) {
        // 结束递归条件
        // 两个为null
        if(left == null && right == null) {
            return true;
        }
        // 其中一个为null或两个不等
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        // 相等处理左左-右右，左右-右左
        return recur(left.left, right.right) && recur(left.right, right.left);
    }
}

0 赞同 0 条回复

Marshan 普通 2023年7月16日上午10:34

感觉有点乱

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

0 赞同 0 条回复

波雅汉库克普通 2023年7月16日上午9:25

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr){
            return true;
        }
        queue<TreeNode*> qLeft;
        queue<TreeNode*> qRight;
        qLeft.push(root->left);
        qRight.push(root->right);
        while(!qLeft.empty()&&!qRight.empty()){
            TreeNode* left = qLeft.front();
            TreeNode* right = qRight.front();
            qLeft.pop();
            qRight.pop();
            if(left == nullptr && right == nullptr){
                continue;
            }
            if(left == nullptr || right == nullptr){
                return false;
            }
            if(left->val!=right->val){
                return false;
            }           
            qLeft.push(left->left);
            qRight.push(right->right);         
            qLeft.push(left->right);
            qRight.push(right->left);

        }
        return true;
    }
};

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

0 赞同 0 条回复

ppopp 普通 2023年7月16日上午1:37

解答：
class Solution {
public:
bool check(TreeNode *p, TreeNode *q) {
if (!p && !q) return true;
if (!p&&q || !q&&p) return false;
return p->val q->val && check(p->left, q->right) && check(p->right, q->left);
}

bool isSymmetric(TreeNode* root) {
    return check(root, root);
}

};

0 赞同 0 条回复

周小二普通 2023年7月16日上午12:21

代码：

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年7月15日下午6:28

Day7：下面是代码

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

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

0 赞同 0 条回复

人生何处不青山普通 2023年7月15日下午6:14

ts写的

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSymmetric(root: TreeNode | null): boolean {
    return dfs(root,root);
};

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

0 赞同 0 条回复

北辰普通 2023年7月15日下午5:42

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

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

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

June 普通 2023年7月15日下午4:27

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil{
        return true
    }

    return treeSymmetric(root,root)
}

func treeSymmetric(root1 *TreeNode , root2 *TreeNode) bool {
    if (root1 == nil && root2 !=nil) || (root1 != nil && root2 ==nil) {
        return false
    }
    if( root1 == nil && root2 == nil){
        return true
    }
    if root1.Val != root2.Val {
        return false
    }

    var ans1 bool = treeSymmetric(root1.Left,root2.Right)
    var ans2 bool = treeSymmetric(root1.Right,root2.Left)

    if(ans1 == false || ans2 == false){
        return false    
    }

    return true
}

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

0 赞同 0 条回复

AD钙奶普通 2023年7月15日下午4:01

判断特殊情况，左右子树均为空，即只有一个根节点，对称
任一子树为空，不对称
任一子树都不为空，但值不同，不对称
递归遍历子树的对应节点。理解对称的含义，左右两边，是哪两个节点比较，这点要搞清楚。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return cmp(root.left,root.right);
    }
    public boolean cmp(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 cmp(left.left,right.right) && cmp(left.right,right.left);
    }
}

0 赞同 0 条回复

Mooby 普通 2023年7月15日下午2:15

七
/**
* 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 root null ? true : recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
if (L null && R null)
return true;
if (L null || R null || L.val != R.val)
return false;
return recur(L.left, R.right) && recur(L.right, R.left);
}

}

0 赞同 0 条回复

普通 2023年7月14日下午11:38

c++ 代码


class Solution {
    vector v;
public:
    bool isSymmetric(TreeNode* root) 
    {
       return rootNULL?true:isFull(root->left,root->right);}
bool isFull(TreeNode* L,TreeNode* R)
{
       if(L==NULL&&R==NULL) return true;
       if(L==NULL||R==NULL||L->val!=R->val) return  false;
       return isFull(L->left,R->right)&&isFull(L->right,R->left);
}

};

0 赞同 0 条回复

#00456B 普通 2023年7月14日下午10:23

/**
 * 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 1;
        }
        return check(root->left,root->right);
    }
    bool check(TreeNode* p, TreeNode* q){
        if(!p && !q){ // p q 都为空
            return 1;
        }
        else if(p && q){// p q 都不为空
            return p->val == q->val && check(p->left,q->right) && check(p->right,q->left);
            //检查pq的值是否相同，以及pq的左右是否对称
        }
        else{// p q 一个为空
            return 0;
        }
    }
};

0 赞同 0 条回复

阿尚普通 2023年7月14日下午8:10

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);//判断左右子树是否对称
    }

    public boolean isSymmetric(TreeNode leftTree, TreeNode rightTree){
        if(leftTree == null && rightTree == null) return true;
        if(leftTree == null || rightTree == null) return false;
        if(leftTree.val != rightTree.val) return false;

        boolean outNode = isSymmetric(leftTree.left, rightTree.right);
        boolean inNode = isSymmetric(leftTree.right, rightTree.left);

        return outNode && inNode;
    }
}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月14日下午7:51

”’java
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root null){
return true;
}
return isSymmetricTwoNodes(root.left,root.right);

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

}
”’
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

CKX 普通 2023年7月14日下午5:40

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }

    return traverse(root.Left, root.Right)
}

func traverse(A, B *TreeNode) bool {

    if A == nil && B == nil {
        return true
    }

    if A == nil || B == nil {
        return false
    }

    if (A.Val == B.Val) && traverse(A.Left, B.Right) && traverse(A.Right, B.Left) {
        return true
    }
    return false
}

时间O(n)
空间O(n)

0 赞同 0 条回复

Luminous 普通 2023年7月14日下午5:29

/**
 * 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 check(root.left,root.right);
    }

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

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月14日下午5:01

遍历左右子树，左子树的左子树和右子树的右子树比较
public boolean isSymmetric(TreeNode root) {
//左右子树都要是镜像的
if(rootnull)
{
return true;
}
return isSymmetric1(root.left,root.right);

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

}

0 赞同 0 条回复

ONE PIECE 普通 2023年7月14日下午4:50

/**
 * 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 is(root.left,root.right);
    }

    public boolean is(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 is(l.left,r.right) && is(l.right,r.left);
    }
}

时间复杂度：O(n);

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月14日下午4:40

通过「同步移动」两个指针的方法来遍历这棵树，pp 指针和 qq 指针一开始都指向这棵树的根，随后 pp 右移时，qq 左移，pp 左移时，qq 右移。每次检查当前 pp 和 qq 节点的值是否相等，如果相等再判断左右子树是否对称
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) {
    return check(root, root);
}

};

0 赞同 0 条回复

Recluse 普通 2023年7月14日下午4:15

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

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

0 赞同 0 条回复

V2ero 普通 2023年7月14日下午3:05

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

function isSymmetric(root: TreeNode | null): boolean {
    if (!root) {
        return true;
    }

     /**
       * 转换为判断两颗树是否对称
       */
    const check = (left: TreeNode | null, right: TreeNode | null) => {
        /**
         * 根节点相同，左节点等于右节点
         */
        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)
        );
    };

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

0 赞同 0 条回复

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

共以下 35 个回答

# 回答此问题取消回复

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

共以下 35 个回答

# 回答此问题 取消回复

# 回答此问题取消回复