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

LovLe 普通 2024年12月22日下午2:01

迭代法（不是层序遍历）

6

7 7

8 8 9 9

任意的左右子树，都是这个规则，左左–右右，左右-右左。可以模拟第四层

# 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 checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        stack=[]
        stack.append(root.left)
        stack.append(root.right)
        while stack:
            rcur=stack.pop()
            lcur=stack.pop()
            if not rcur and not lcur: continue
            if not rcur or not lcur: return False
            if rcur.val != lcur.val: return False   #值不相等，不对称

            stack.append(lcur.left) #左孩子左节点
            stack.append(rcur.right)    #右孩子右节点
            stack.append(lcur.right)    #左孩子右节点
            stack.append(rcur.left) #右孩子左节点

            #     if cur.left: stack.append(cur.left)
            #     if cur.right: stack.append(cur.right)
            # chlen=len(stack)
            # if chlen%2!=0: return False
            # for i in range(chlen//2):
            #     if stack[i].val!=stack[chlen-i-1].val:
            #         return False
        return True

递归法

这个思路就非常清晰了。参考迭代法的思路。

递归的对象是（左左，右右）和（左右，右左）子树

# 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,l,r):
        if not l and not r: return True
        if not l or not r or l.val!=r.val : return False
        return self.isSymmetric(l.left,r.right) and self.isSymmetric(l.right,r.left)
    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:
        if not root: return True        
        return self.isSymmetric(root.left,root.right)

0 赞同 0 条回复

mpweixin用户普通 2024年12月14日下午4:24

递归
1、传入要比较的两个子树，返回bool
2、终止条件：全空为真，一空一非空为假，都不空时结点值相同为假。
3、外层递归传入（左树的左，右树的右），内层递归传入（左树的右，右树的左），两者取&作返回值

class Solution {
public:
    bool checkSymmetricTree(TreeNode* root) {
        if(root == NULL) return true;
        return compare(root->left, root->right);
    }

    bool compare(TreeNode* left, TreeNode* right){
        if(left == NULL && right ==NULL) return true;
        else if(left == NULL || right == NULL) return false;
        if(left->val != right->val) return false;
        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        return outside && inside;
    }
};

0 赞同 0 条回复

岱永久会员 2024年12月11日下午5:29

LCR 145. 判断对称二叉树

递归

class Solution {
    public boolean checkSymmetricTree(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 条回复

陆狗陆狗普通 2024年12月4日上午10:13

题解

class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        // 无节点
        if(root==null){
            return true;
        }

        // 存在2个子树
        return isEquals(root.left,root.right);

    }

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

0 赞同 0 条回复

🌟 普通 2024年12月3日下午8:27

“`java
递归
class Solution {
public:
bool checkSymmetricTree(TreeNode* root) {
if (!root)
return true;
return recue(root->left, root->right);
}
bool recue(TreeNode* L, TreeNode* R) {
if (!L && !R)
return true;
if (!L || !R || L->val != R->val)
return false;
return recue(L->left, R->right) && recue(L->right, R->left);
}
};

0 赞同 0 条回复

Pendulumpal 普通 2024年12月2日下午8:35

构造一个镜像的翻转树，逐个节点比较

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode filptree(TreeNode node){
        if(node==null)return null;
        TreeNode l=filptree(node.left);
        TreeNode r=filptree(node.right);
        node.left=r;
        node.right=l;
        return node;
    }
    public boolean doit(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;
        else return doit(root1.left,root2.right)&&doit(root1.right,root2.left);
    }
    public boolean checkSymmetricTree(TreeNode root) {
        TreeNode rootplus=root;
        rootplus=filptree(rootplus);
        return doit(root,rootplus);
    }
}

0 赞同 0 条回复

Tom Yuan 普通 2024年12月1日上午5:15

方法递归对着left和right递归在递归函数中进行条件的判断，注意一些条件的顺序不然有可能会被覆盖掉结果导致错误。

class Solution:
    def checkSymmetricTree(self, root: Optional[TreeNode]) -> bool:
        if not root or (not root.left and not root.right): return True

        return self.check(root.left, root.right)

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

        return self.check(left.left, right.right) and self.check(left.right, right.left)

time O(n) space O(n)

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午7:33

/**


方法一：递归
如果同时满足下面的条件，两个树互为镜像：
    它们的两个根结点具有相同的值
    每个树的右子树都与另一个树的左子树镜像对称

 */
class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        return helper(root, root);
    }

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


    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年11月29日下午12:44

思路：通过指定对称指针进行对称结点等空等值的判断，从而实现对称二叉树的判断
class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        return checkEqual(root,root);
    }

    public boolean checkEqual(TreeNode p,TreeNode q){
        if(p==null&&q==null) return true;
        if(p==null||q==null) return false;
        else return (p.val==q.val&&checkEqual(p.right,q.left)&&checkEqual(p.left,q.right));
    }
   时间复杂度：O（n）
   空间复杂度：O（n）

0 赞同 0 条回复

黑键〰普通 2024年11月29日上午11:25

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var checkSymmetricTree = function(root) {
    if(!root) return true;
    let check = (p, q) => {
        if(!p && !q) return true; // 先判断是否都为Null
        if(!p || !q) return false; // 再判断是不是其中一个为Null
        return p.val === q.val && check(p.left, q.right) && check(p.right, q.left);
    }
    return check(root, root);
};

思路：类似的递归套路，但是相对于之前，这次是需要分别对对称位置的子树递归来比较，还需要比较当前节点的值
时间复杂度O(N)，空间也是O(N)

0 赞同 0 条回复

Renasc 普通 2024年11月29日上午9:05

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

class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        return check(root, root);
    }

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

无言永久会员 2024年11月28日下午9:01

class Solution {
public:
    bool isMirrorTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr) {
            return true;
        } else if(p == nullptr || q == nullptr) {
            return false;
        } 
        return (p->val == q->val) && isMirrorTree(p->left, q->right) && isMirrorTree(p->right, q->left);
    }
    bool checkSymmetricTree(TreeNode* root) {
        if(root == nullptr) return true;
        return isMirrorTree(root->right, root->left);
    }
};
时间复杂度：O(n) 
空间复杂度：O(n)

0 赞同 0 条回复

苯庸普通 2024年11月28日下午8:24

class Solution {
public boolean checkSymmetricTree(TreeNode root) {
if(root null){
return true;
}
return isSame(root.left, root.right);
}

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

}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

Kisara 普通 2024年11月28日下午7:13

双指针镜像遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean checkSymmetricTree(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);
    }
}

OnOn

0 赞同 0 条回复

Aatorx 永久会员 2024年11月28日下午4:10

class Solution {
public:
    bool checkSymmetricTree(TreeNode* root) {
        if (root == nullptr){
            return true;
        }
        return recur(root->left, root->right);
    }
    bool recur(TreeNode* l, TreeNode* r){
        if(l == nullptr && r == nullptr){
            return true;
        }
        if((l == nullptr && r != nullptr) || (r == nullptr && l != nullptr)){
            return false;
        }
        if (l->val != r->val){
            return false;
        }
        return recur(l->right, r->left) && recur(l->left, r->right);
    }
};

时间复杂度O(N)，空间复杂度O(H)。

0 赞同 0 条回复

Jerry 普通 2024年11月28日下午4:09

class Solution {
public:
    bool checkSymmetricTree(TreeNode* root) {
        if(!root) return true;
        return check(root->left, root->right);
    }
    bool check(TreeNode* node1, TreeNode* node2){
        if(!node1 && !node2) return true;
        if(!node1 || !node2) return false;

        if(node1->val != node2->val){
            return false;
        }
        return check(node1->left, node2->right)&&check(node1->right, node2->left);
    }
};

时间o(n)
空间o(n)

0 赞同 0 条回复

月下足迹普通 2024年11月28日上午11:14

//时间复杂度 O(N)

class Solution {
public boolean checkSymmetricTree(TreeNode root) {
if (root null) {
return true;
}

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

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

    if (left == null || right == null || left.val != right.val) {
        return false;
    }

    return check(left.left, right.right) && check(left.right, right.left);

}

}

0 赞同 0 条回复

jaron 普通 2024年11月28日上午10:33

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

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

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

youngsir 普通 2024年11月28日上午9:33

打卡

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


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

    }
};

时间复杂度O（n），空间复杂度O（lgn））(最坏情况O（n）)

0 赞同 0 条回复

lQl 永久会员 2024年11月27日下午11:33

递归判断左右子树是否相等,但是比较算法的左右子树要倒过来
时间复杂度O(n)
空间复杂度O(n)

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

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

}

0 赞同 0 条回复

休一普通 2024年11月27日下午10:08

class Solution {
public:
    bool checkSymmetricTree(TreeNode* root) {

        return dfs(root,root);
    }
    bool dfs(TreeNode* A,TreeNode* B)
    {
//如果能够递归到叶子节点，代表其为对称二叉树返回true
        if(A == nullptr && B == nullptr) return true;
//如果A和B其中一个为叶子节点，另一个不是的话 以及A和B的值不相同，返回false
        if( A==nullptr || B==nullptr || A->val != B->val){
            return false;
        } 

        return dfs(A->left,B->right) && dfs(A->right,B->left);
    }
};
//时间复杂度o(n),空间复杂度o(n)

0 赞同 0 条回复

晓宇普通 2024年11月27日下午8:47

···cpp
class Solution {
public:
bool isEqualNode(TreeNode* left, TreeNode* right){
if(!left && !right) return true;
else if(!left || !right) return false;
else if(left->val != right->val) return false;

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

}

bool checkSymmetricTree(TreeNode* root) {
    if(!root || (!root->left && !root->right)) return true;
    return isEqualNode(root->left, root->right);

}

};
// 思路：先判断当前节点的左右节点是否对称，再判断左左和右右及左右和右左，依次类推。
// 时间复杂度：o(n)
// 空间复杂度：o(lgn)

“`

0 赞同 0 条回复

秋山丽奈普通 2024年11月27日下午8:30

思路：递归首先判断当前两个节点nodeLeft.val nodeRight.val 是否相同，若相同则比较 nodeLeft.left, nodeRight.right && nodeLeft.right, nodeRight.left 是否相同

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

    boolean check(TreeNode nodeLeft, TreeNode nodeRight){
        if(nodeLeft == null && nodeRight == null){
            return true;
        }else if(nodeLeft == null || nodeRight == null){
            return false;
        }

        if(nodeLeft.val == nodeRight.val){
            // 递归 子节点 
            return check(nodeLeft.left, nodeRight.right) && check(nodeLeft.right, nodeRight.left);
        }else{
            return false;
        }

    }
}

0 赞同 0 条回复

迢迢星野普通 2024年11月27日下午8:12

class Solution {
    /**
     * 请设计一个函数判断一棵二叉树是否 轴对称 。
     * 
     * @param root
     * @return
     */
    public boolean checkSymmetricTree(TreeNode root) {
        if (root == null)
            return true;
        return check(root.left, root.right);
    }

    private boolean check(TreeNode left, TreeNode right) {
        if (left == null || right == null) {
            return left == right;
        }
        // 比较左右节点的值
        if (left.val != right.val) {
            return false;
        }
        // 左右子树也需要镜像对称
        return check(left.left, right.right) && check(left.right, right.left);
    }

    // 使用队列实现非递归方法
    private boolean compare(TreeNode root) {
        // 使用队列
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root.left);
        que.offer(root.right);

        while (!que.isEmpty()) {
            TreeNode left = que.poll();
            TreeNode right = que.poll();

            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null || left.val != right.val) {
                return false;
            }

            // 插入新节点
            que.offer(left.left);
            que.offer(right.right);
            que.offer(left.right);
            que.offer(right.left);
        }
        return true;
    }
}

递归

递归地判断两颗子树是否镜像对称，判断两颗子树的根节点是否相等之后，还需要递归地检查左子树的左子树和右子树的右子树是否对称，以及左子树的右子树和右子树的左子树是否对称。
时间复杂度：O(n)，遍历二叉树的每个节点。
空间复杂度：O(n)（最坏情况）或 O(logn)（平均情况）。

迭代

使用队列来逐个遍历二叉树节点，判断二叉树是否镜像对称。
时间复杂度：O(n)，遍历二叉树的每个节点。
空间复杂度：O(n)（最坏情况）或 O(logn)（平均情况）。

0 赞同 0 条回复

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

共以下 24 个回答

迭代法（不是层序遍历）

递归法

LCR 145. 判断对称二叉树

递归

迭代

# 回答此问题取消回复

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

共以下 24 个回答

迭代法（不是层序遍历）

递归法

LCR 145. 判断对称二叉树

递归

迭代

# 回答此问题 取消回复

# 回答此问题取消回复