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

宁永久会员 2023年3月10日上午10:38

判断是否对称，采用双指针的思想

public boolean isSymmetric(TreeNode root) {
        //同步移动两个指针 一个左移一个右移。
        return check(root, root);
    }
    public boolean check(TreeNode p, TreeNode q){
        //终止条件，遇到null
        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 条回复

lucca 普通 2023年1月3日下午3:29

O(N) 构造 + 检查

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

    private TreeNode mirror(TreeNode root) {
        if (root == null) return null;
        TreeNode node = new TreeNode(root.val);
        node.left = mirror(root.right);
        node.right = mirror(root.left);
        return node;
    }

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

O(N) 迭代

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

    private boolean check(TreeNode root, TreeNode copy) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        q.offer(copy);
        while (!q.isEmpty()) {
            TreeNode u = q.poll();
            TreeNode v = q.poll();
            if (u == null && v == null) continue;
            if ((u == null || v == null) || (v.val != u.val)) return false;

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}

0 赞同 0 条回复

PatNick 普通 2022年12月20日下午5:48

def isSymmetric(root: TreeNode) -> bool:
    if root == None or (root.left == None and root.right == None):
        return True

    return f(root.left,root.rigth)


# 判断A，B是否值相同
def f(A,B):
    if A == None and B == None:
        return True
    if A == None or B == None:
        return False
    if A.val != B.val:
        return False
    return f(A.left,B.right) and f(A.right,B.left)

0 赞同 0 条回复

如梦似歌普通 2022年12月15日下午4:42

class Solution {
    /**
     *对于对称二叉树中任意两个对称结点L和R,一定有:
     *      L.val == R.val
     *      L.left.val = R.right.val
     *      L.right.val=R.left.val
     * 根据以上规律，考虑从顶至底递归，判断每队结点是否对称，从而判断该树是否为对称二叉树。
     * 复杂度分析:
     * 时间复杂度: T(n) = O(n) 每次执行 dfs() 可以判断一对节点是否对称，因此最多调用 N/2 次 recur() 方法
     * 空间复杂度: S(n) = O(n) 最差情况下(当二叉树退化为链表时)，递归需要使用O(n)大小的占空间。
     */
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;  //若根结点为空那个，则直接返回true
        }else{
            return dfs(root.left,root.right); //否则从上至下递归遍历左右子树
        }
    }

    public boolean dfs(TreeNode L, TreeNode R){
        if(L == null && R == null)  //当L和R同时越过叶子结点，则表示此树从顶至低的结点都对称，因此返回true
            return true;
        if(L == null || R == null || L.val != R.val)  //当L或者R中只有一个结点越过叶子结点，此树不对称; 或则当结点L的值不等于结点R的值时，返回false
            return false;
        return dfs(L.left,R.right) && dfs(L.right,R.left); //当两队结点都对称时，才是对称树，因此用逻辑与符号相连
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:11

class Solution {
public:
    bool traversal(TreeNode* left, TreeNode* right){ //参数
        if(left==nullptr && right==nullptr) return true;
        else if(left==nullptr && right!=nullptr) return false;
        else if(left!=nullptr && right == nullptr) return false;
        else if(left->val!=right->val) return false;
        else{
            bool leftflag = traversal(left->left, right->right);
            bool rightflag = traversal(left->right,right->left); //需要同时判断左右子树是否对称
            bool flag = (leftflag && rightflag);
            return flag;
        }
    }

    bool isSymmetric(TreeNode* root) {
        //思路：递归三部曲
        if(root==nullptr) return true;
        bool flag = traversal(root->left, root->right);
        return flag;
    }
};

0 赞同 0 条回复

cute. 普通 2022年11月12日下午9:25

var isSymmetric = function(root) {
    if(root == null || (root.left == null && root.right == null)) {
        return true;
    }
    return isSame(root.left, root.right);
};
var isSame = 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 isSame(A.left, B.right) && isSame(A.right, B.left);
}

时间复杂度:O(n)
空间复杂度:O(n)【n为树的高度】

0 赞同 0 条回复

xye 普通 2022年11月12日下午8:06

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return check(root.Left, root.Right)
}

func check(p, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    //判定不是对称：1.一边是空（只有一个越过叶节点）；2，值不同
    if p == nil || q == nil || p.Val != q.Val {
        return false
    }
    return check(p.Left, q.Right) && check(p.Right, q.Left)
}

时间O(N)空间O(N)

0 赞同 0 条回复

symbol 普通 2022年11月7日下午1:04

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return Help(root.Left, root.Right)
}
func Help(left *TreeNode, right *TreeNode) bool{
    if left == nil && right == nil {
        return true
    }
    if left == nil && right != nil {
        return false
    }
    if left != nil && right == nil {
        return false
    }
    if left.Val != right.Val {
        return false
    }
    //要是略过了以上条件 则继续递归
    in_Sym := Help(left.Right, right.Left)  //是否内对称
    out_Sym := Help(left.Left, right.Right) //是否外对称

    return in_Sym && out_Sym
}

0 赞同 0 条回复

Asphyxia 普通 2022年11月5日下午11:00

没想到需要两个节点

/**
 * 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) {
        queue<TreeNode*> q;
        TreeNode* node1 = root;
        TreeNode* node2 = root;
        q.push(node1);
        q.push(node2);
        while(!q.empty()){
            node1 = q.front();
            q.pop();
            node2 = q.front();
            q.pop();
            if(!node1&&!node2) continue;
            if((!node1||!node2)||(node1->val!=node2->val)) return false;
            q.push(node1->left);
            q.push(node2->right);
            q.push(node1->right);
            q.push(node2->left);
        }
        return true;
    }
};

0 赞同 0 条回复

lobort 普通 2022年11月4日下午10:21

class Solution {
    public boolean isSymmetric(TreeNode root) {
        //判断特殊情况 
        if(root == null || root.left == null && root.right == null){
            return true;
        }
        return func(root.right, root.left);    
    }
    public boolean func(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;
        }
        //注意对称二叉树是 A的right 和 B的left相比较
        return func(A.left, B.right) && func(A.right, B.left);
    }
}

0 赞同 0 条回复

星河普通 2022年11月3日下午10:16

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);
    }
}
时间O(N)空间O(N)

0 赞同 0 条回复

感到自己好渺小普通 2022年11月3日上午11:47

class Solution {
    //判断对称二叉树的条件
    //1.L.val == R.val
    //2.L.left.val == R.right.val
    //3.L.right.val == R.left.val

    //递归三部曲
    //1.递归函数的功能: 判断传入的两个树是否镜像
    //传入的参数 TreeNode left TreeNode right 返回true or false
    //2.递归的终止条件: 
    //(1)左右结点同时为空(同时越过了叶子结点) && 值相同 -> true
    //(2)左节点为空时右节点不为空，或反之 -> false
    //(3)左右结点的值不相等 -> false
    //3.函数等价关系式
    //(1)要想两棵树镜像，那么一棵树的左边要和第二课树的右边镜像 recur(L.left,R.right)
    //(2)一棵树的右边要和第二棵树的左边镜像 recur(L.right,R.left);
    public boolean isSymmetric(TreeNode root) {
        //如果根节点为空，那么属于对称二叉树
            if(root == null) return true;
            return recur(root.left,root.right);
    }
    public boolean recur(TreeNode L,TreeNode R){
        if(L == null && R == null) return true;  //如果左右结点同时越过叶子结点，说明对称，返回true
        if(L == null || R == null) return false; //如果只有一个节点为空，另一个不为空，那么不对称
        if(L.val != R.val) return false;     //如果左右节点的值不相等，那么不对称
        else return recur(L.left,R.right)&&recur(L.right,R.left);  //进行条件2，3的判断
    }
}

0 赞同 0 条回复

一只骆驼普通 2022年11月2日下午7:32

简单递归

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

0 赞同 0 条回复

cxxz 普通 2022年11月1日下午11:44

由于是对称，需要两个子树，另借助一个接收两个树节点的递归函数。主要的判断条件就是从两个比较的根节点开始判断，相同则递归判断左子树的左子树与右子树的右子树，左子树的右子树与右子树的左子树。base 有很多种，最重要的就是递归到同时全为NULL证明对称，其中一个为NULL证明没有对上，根值不同一定不对称。

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

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

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

0 赞同 0 条回复

虾仁猪心普通 2022年11月1日下午6:53

思路：
递归三要素：
1. 明确你这个函数想要干什么: 对比左子树和右子树是否是镜像
2. 寻找递归结束条件：
+ 当 L和 R 同时越过叶节点：此树从顶至底的节点都对称，因此返回 true；
+ 当 L 或 R中只有一个越过叶节点：此树不对称，因此返回 false ；
+ 当节点 L的值！= 节点 R的值：此树不对称，因此返回 false

找出函数的等价关系式：
- 判断两节点 L.leftL.left 和 R.rightR.right 是否对称，recur(L.left, R.right);
- 判断两节点 L.rightL.right 和 R.leftR.left 是否对称，recur(L.right, R.left);

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null ? true: recur(root.left,root.right);
    }
    public 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 条回复

酥合普通 2022年10月31日下午10:31

/**
 * 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 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);
    }
}

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

0 赞同 0 条回复

Y7n05h 普通 2022年10月31日下午10:24

class Solution {
    bool isSymmertric(TreeNode *root1, TreeNode *root2) {
        if (!!root1 != !!root2) return false;
        if (!root1) return true;
        if (root1->val != root2->val) return false;
        return isSymmertric(root1->left, root2->right) && isSymmertric(root1->right, root2->left);
    }

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

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

0 赞同 0 条回复

Whatever 永久会员 2022年10月31日下午4:19

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

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 left == right;
        }
        if(left.val != right.val){
            return false;
        }
        return compare(left.left,right.right) && compare(left.right,right.left);
    }

}

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午3:06

 public boolean isSymmetric(TreeNode root) {

        //1.先寻找递归结束的条件
        if (root == null) return true;

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

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

0 赞同 0 条回复

刺猬普通 2022年10月31日下午2:59

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

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

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

0 赞同 0 条回复

庄重普通 2022年10月31日下午12:32

//  思路：
//     函数功能：判断左右子树是否对称
//     关系式 f(lNode->left,rNode->right) && f(lNode->right,rNode->left) -->true or false
//     初始值
//         调用函数：
//              root == NULL || (root->left == NULL && root->right == NULL)
//         递归函数：
//             if(lNode == NULL && rNode == NULL) return true;
//             if(lNode == NULL || rNode == NULL) return false;
//             if(lNode->val != rNode->val) return false;
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL || (root->left == NULL && root->right == NULL))
            return true;

        return f(root->left,root->right);
    }

    bool f(TreeNode* lNode, TreeNode* rNode){
        if(lNode == NULL && rNode == NULL) return true;
        if(lNode == NULL || rNode == NULL) return false;
        if(lNode->val != rNode->val) return false;
        //三个判断关系中(lNode->val != rNode->val)的位置必须放到最后
        //先判断空的情况，再判断非空时的情况，否则会出现指针错误

        if(f(lNode->left,rNode->right) && f(lNode->right,rNode->left)){
            return true;
        }
        return false;

    }
};
//时间复杂度:O(logn)
//空间复杂度:O(n)

0 赞同 0 条回复

云雾里普通 2022年10月31日上午7:26

class Solution {
//递归
    public boolean isSymmetric(TreeNode root) {
        return root==null?true:digui(root.left,root.right);
    }
    private boolean digui(TreeNode l,TreeNode r){
        if(l==null&&r==null)return true;
        if(l==null || r==null || l.val!=r.val)return false;
        return digui(l.left,r.right)&&digui(l.right,r.left);
    }
    /*public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }*/
}

0 赞同 0 条回复

绍熙普通 2022年10月31日上午6:59

思路：从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树

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

猫猫真可爱普通 2022年10月30日下午9:01

递归遍历，分别遍历左右子树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return Symmetric(root,root);
    }
    public boolean Symmetric(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 Symmetric(root1.left,root2.right) && Symmetric(root1.right,root2.left);
    }
}

0 赞同 0 条回复

小肸永久会员 2022年10月30日下午5:25

思路：就是模拟。只不过实现方式不同，可以递归，可以迭代。递归实现的时间复杂度O（N），空间复杂度O(height）。

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

0 赞同 0 条回复

@ 普通 2022年10月30日下午4:23

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

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

Chin 普通 2022年10月30日下午3:07

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

    public boolean is(TreeNode left,TreeNode right){
        if(left==null && right==null) return true;
        if(left==null || right==null) return false;
        //  左子树等于左子树 && 左子树的左节点=右子树的右节点  && 左子树的右节点 = 右子树的左节点
        return left.val == right.val && is(left.left,right.right) && is(left.right,right.left);
    }
}

时间复杂度On
空间复杂度On

0 赞同 0 条回复

cxc 普通 2022年10月30日下午2:56

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

//检查左右子树是否对称
public boolean check(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 check(node1.left, node2.right) && check(node1.right, node2.left);
    }
}

0 赞同 0 条回复

天然普通 2022年10月30日下午12:03

学习新思想，做好每道题,迭代的想法，时间复杂度O(n),空间复杂度O(n)

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root or not (root.left or root.right): return True
        num = [root.left,root.right]
        while num:
            tem1 = num.pop(0)
            tem2 = num.pop(0)
            if not (tem1 or tem2):
                continue
            if not (tem1 and tem2) or tem1.val != tem2.val:  #有左没右，有右没左
                return False
            num.append(tem1.left)
            num.append(tem2.right)
            num.append(tem1.right)
            num.append(tem2.left)
        return True

0 赞同 0 条回复

wxc 普通 2022年10月30日上午9:45

啊

class Solution:
    def check(self, a:TreeNode, b:TreeNode) -> bool:
        if not a and not b:
            return True
        if not a or not b:
            return False
        if a.val == b.val:
            return self.check(a.left,b.right) and self.check(a.right,b.left)
        else:
            return False
    def isSymmetric(self, root: TreeNode) -> bool:
        if root:
            return self.check(root.left, root.right)
        return True

0 赞同 0 条回复

yanshuojune 普通 2022年10月30日上午12:16

解题思路：考虑从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树。
时间复杂度：O（n）
空间复杂度：O（n）

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 考虑从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树。
        def recur(L,R):
            if not L and not R:
                return True
            if not L or not R or L.val != R.val:
                return False
            return recur(L.left,R.right) and recur(L.right,R.left)

        return recur(root.left, root.right) if root else True

0 赞同 0 条回复

T 普通 2022年10月29日下午8:44

下面代码

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

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

}

0 赞同 0 条回复

派大星普通 2022年10月29日下午8:22

class Solution {
//二叉树左右对称，判断左子树与右子树是不是完全一致。
//时间复杂度O(n)
//空间复杂度O(n)
    public boolean isSymmetric(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null)){
            return true;
        }
        return isTrue(root.left,root.right);

    }

    public boolean isTrue(TreeNode r1,TreeNode r2){
        if(r1==null&&r2!=null){
            return false;
        } else if (r2==null&&r1!=null) {
            return false;
        } else if (r1==null&&r2==null) {
            return true;
        }
        if(r1.val!=r2.val)return false;

        Boolean b1 = isTrue(r1.left,r2.right);
        if(b1==false)return b1;
        Boolean b2 = isTrue(r1.right,r2.left);
        if(b2==false)return b2;

        return true;
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年10月29日下午7:41

public boolean isSymmetric(TreeNode root) {
        //时间复杂度O(n) 遍历所有节点
        //空间复杂度O(n)//调用栈是整个树的所有节点
        if (root == null) return true;

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

    }

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

0 赞同 0 条回复

Gg 普通 2022年10月29日下午6:48

 // 遍历整颗树时间复杂度为On
 // 递归空间复杂度为On
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSym(root.left,root.right);
    }

    public boolean isSym(TreeNode left,TreeNode right){
        // 递归终止条件及当前层处理
        if(left == null && right == null){
            return true;
        }
        if((left == null && right != null) || (left!= null && right == null)){
            return false;
        }
        if(left.val == right.val){
            // 进入递归函数
            return isSym(left.left,right.right) && isSym(left.right,right.left);
        }
        return false;
    }
}

0 赞同 0 条回复

阿白普通 2022年10月29日下午6:03

前序遍历，对俩子节点递归比较是否一致。
时间O（n），空间O（1）

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

        return funcSym(root->left, root->right);
    }

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

0 赞同 0 条回复

你有点可爱喔普通 2022年10月29日下午5:59

class Solution {
    public boolean isSymmetric(TreeNode root) {
            if(root == null) return true;

            //找出镜像 
            return compareTo(root.left,root.right);
    }
    public boolean compareTo(TreeNode r1,TreeNode r2){
        //左右子树为空的情况下
        if(r1 == null && r2 == null){
            return true;
        }
        if(r1 == null || r2 == null){
            return false;
        }
        return r1.val == r2.val && compareTo(r1.left,r2.right) && compareTo(r1.right,r2.left);
    }


}

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

0 赞同 0 条回复

Tolkien 永久会员 2022年10月29日下午5:46

/**
     * 递归
     * 时间复杂度：O(n)
     * 空间复杂度：O(logn)
     */
    public boolean isSymmetric(TreeNode root) {
        // 1. 递归结束条件
        if (root == null) {
            return true;
        }


<pre><code>    // 2. 等价关系式
    // 一颗二叉树是对称的当且仅当他的左子树和右子树互为镜像二叉树
    return helper(root.left, root.right);
}

// L和R是否互为镜像的二叉树
public boolean helper(TreeNode L, TreeNode R) {
    // 1. 递归结束条件
    if (L == null && R == null) {
        return true;
    }

    if (L == null || R == null) {
        return false;
    }

    if (L.val != R.val) {
        return false;
    }

    /**
     * 2. 等价关系式
     * L和R互为镜像二叉树 当且仅当
     * 1. L的左子树和R的右子树互为镜像二叉树
     * 2. L的右子树和R的左子树互为镜像二叉树
     */
    return helper(L.left, R.right) && helper(L.right, R.left);
}
</code></pre>

0 赞同 0 条回复

just 普通 2022年10月29日下午3:50

//recursion
递归写法
class Solution {
public:
bool fun(TreeNode* l,TreeNode* r){
if(!l&&!r) return true;
if(!l&&r) return false;
if(l&&!r) return false;
if(l->val!=r->val) return false;
return fun(l->left,r->right)&&fun(l->right,r->left);
}
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return fun(root->left,root->right);

};

0 赞同 0 条回复

Haoyun 普通 2022年10月29日下午1:53

比较内侧和外侧是否对称

var isSymmetric = function(root) {
  if(!root) return true;
  const compare = function(left, right) {
      if(left === null && right !== null) {
          return false;
      } else if(left !== null && right === null) {
          return false;
      } else if(left === null && right === null) {
          return true;
      } else if(left.val !== right.val) {
          return false;
      }

      let outside = compare(left.left, right.right);
      let inside = compare(left.right, right.left); 
      return outside && inside;
  }
  return compare(root.left,root.right);
};

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

0 赞同 0 条回复

是梦终空永久会员 2022年10月29日上午11:46

递归，第一次提交有bug，发现是第三个if得在第四个if之前，不然为空了，第一次没考虑到.
时间O(n)
空间O(n)

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 == right)   return true;
        if(left.val != right.val)   return false;
        return compare(left.left,right.right) && compare(left.right,right.left);
    }
}

0 赞同 0 条回复

追普通 2022年10月29日上午10:34

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

易水寒永久会员 2022年10月29日上午10:24

//if的情况不能想复杂，逐层排除返回情况

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

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

0 赞同 0 条回复

浅夏的无奈普通 2022年10月29日上午12:44

//时间复杂度：O(N)
//空间复杂度：O(N)
//从上向下，可以发现L.right.val=R.left.val，并且L.left.val =R.right.val;
//由此发现递归的传入值有两个L，R；

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return res(root,root);
    }
    public boolean res(TreeNode L,TreeNode R){
        if(L==null && R==null){
            return true;
        }
        if(L==null || R==null){
            return false;
        }
        Boolean flag = L.val == R.val&&res(L.right,R.left)&&res(L.left,R.right);
        return flag;
    }
}

0 赞同 0 条回复

狗蛋儿普通 2022年10月28日下午10:38

class Solution {
public:
    //这个题目其实仍然算是一个后序遍历，表面上来看颇有几分前序的意思
    //return的时候其实省略的
    //仔细分析一下实际上依旧是自下而上的进行判断！
    bool compareTwo(TreeNode* pRoot1,TreeNode* pRoot2){
        if(!pRoot1 && pRoot2) return false;
        else if(pRoot1 && !pRoot2) return false;
        else if(!pRoot1 && !pRoot2) return true;
        else if(pRoot1->val != pRoot2->val) return false;

        bool isOut = compareTwo(pRoot1->left, pRoot2->right);
        bool isIn = compareTwo(pRoot1->right, pRoot2->left);
        return isOut && isIn;
    }
    bool isSymmetrical(TreeNode* pRoot) {
        if(!pRoot) return true;
        return compareTwo(pRoot->left, pRoot->right);
    }

};

0 赞同 0 条回复

青木普通 2022年10月28日下午10:33

/**
    有点难受，想到了需要两个指针进行操作，但是就是判断不出来
    两个节点只有一个肯定就不对

    时间复杂度O(n)
    空间复杂度O(Height)
 */
class Solution {
    public boolean function(TreeNode root1, TreeNode root2){
        if(root1==null && root2==null){
            return true;
        }
        if(root1==null || root2 == null){
            return false;
        }

        return root1.val == root2.val && function(root1.left, root2.right) && function(root1.right, root2.left);
    }

    public boolean isSymmetric(TreeNode root) {
        return function(root, root);
    }
}

/**
    还有个迭代版本的，使用队列，也没做出来...QAQ
 */
class Solution {
    public boolean function(TreeNode r1, TreeNode r2){
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(r1);
        q.offer(r2);
        while(!q.isEmpty()){
            r1 = q.poll();
            r2 = q.poll();
            if(r1==null && r2==null) continue;
            if((r1==null || r2==null) || (r1.val!=r2.val)) return false;
            q.offer(r1.left);
            q.offer(r2.right);

            q.offer(r1.right);
            q.offer(r2.left);
        }
        return true;
    }

    public boolean isSymmetric(TreeNode root) {
        return function(root, root);
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月28日下午10:11

归**

时间复杂度O(N）需要遍历所有节点空间复杂度O(N) 最坏情况为链表

注意点：这个题不能单纯用isSymmetric(root.left) && isSymmetric(root.right)来得出

比较应该分如下几个层次

两边都为null -> true

两边一个为null -> false;

两边节点值不同-> false;

两边节点值相同 -> 左节点的左节点和右节点的右节点判断 && 左节点的右节点和右节点的左节点判断

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return Symmetric(root,root);
    }
    public boolean Symmetric(TreeNode root1,TreeNode root2){//代表左右子树
        if(root1 == null && root2 == null) return true;//都不存在，则对称
        if(root1 != null && root2 == null || root2 != null && root1 == null)
        return false;//有一边为null，不对称
        if(root2.val != root1.val) return false;//当前比较两个节点数值不同，则不对称
        return Symmetric(root2.left,root1.right) && Symmetric(root2.right,root1.left);
    }
}

队列模拟迭代

/**
 * 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;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while(!queue.isEmpty()){
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if(left == null && right == null) continue;
            if(left == null && right != null || left != null && right == null){
                return false;
            }
            if(left.val != right.val){
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月28日下午9:36

1、运用递归求解，先判断终止条件，如果根节点为空或根的左右节点为空，则返回true
2、新建一个函数，用来判断根节点的左右节点是不是对称的
时间复杂度O(n) 空间复杂度O(n)

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

    bool 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 true;

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

    }

};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月28日下午9:26

时间复杂度为O（n），空间复杂度为O（lgn）

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

黎昕普通 2022年10月28日下午9:11

递归思想解决，需要注意的是这道题给出的是根节点，我被诱导考虑只用一个根节点怎么实现这道题递归。后来反应过来这是不行的，因为判断左-左?=右-右与左-右?=右-左，需要传进去两棵树，所以需要自己重写一个函数。

时间 O(n)
空间如果考虑递归调用栈的压栈空间可能需要O(n)，不计算压栈空间就是O(1)

// 这道题有一个比较坑的地方是：这里的递归是需要使用左右子树的，但是却给出root来诱导
bool isMirror(struct TreeNode* roota,struct TreeNode* rootb){
    if(roota==NULL&&rootb==NULL)return true;
    else if(roota!=NULL&&rootb==NULL||roota==NULL&&rootb!=NULL)return false;
    else if(roota->val!=rootb->val)return false;
    else return isMirror(roota->left,rootb->right)&&isMirror(roota->right,rootb->left);
}

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

做递归思考三步：

递归的函数要干什么？
函数的作用是判断传入的两个树是否镜像。
输入：TreeNode left, TreeNode right
输出：是：true，不是：false
递归停止的条件是什么？
左节点和右节点都为空 -> 倒底了都长得一样 ->true
左节点为空的时候右节点不为空，或反之 -> 长得不一样-> false
左右节点值不相等 -> 长得不一样 -> false
从某层到下一层的关系是什么？
要想两棵树镜像，那么一棵树左边的左边要和二棵树右边的右边镜像，一棵树左边的右边要和二棵树右边的左边镜像
调用递归函数传入左左和右右
调用递归函数传入左右和右左
只有左左和右右镜像且左右和右左镜像的时候，我们才能说这两棵树是镜像的
调用递归函数，我们想知道它的左右孩子是否镜像，传入的值是root的左孩子和右孩子。这之前记得判个root==null。
-----摘自本题目leetcode评论 Tai_Park

0 赞同 0 条回复

So 普通 2022年10月28日下午8:45

/**
 * 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);
    }

    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)，空间：O(n)

0 赞同 0 条回复

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

共以下 51 个回答

O(N) 构造 + 检查

O(N) 迭代

# 回答此问题取消回复

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

共以下 51 个回答

O(N) 构造 + 检查

O(N) 迭代

# 回答此问题 取消回复

# 回答此问题取消回复