讨论/《二叉树》 - 对称二叉树/
《二叉树》 - 对称二叉树
共 17 个回复

解题思路

递归法。两个节点同时为空true,两个节点其中一个为空false
两个节点相等 且 左节点的左子树等于有节点的右子树 且 左节点的右子树等于右节点的左子树,为镜像返回true。
时间复杂度O(n),空间复杂度O(1)。

代码

/**
 * 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 isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
                && isMirror(t1.left, t2.right)
                && isMirror(t1.right, t2.left);
    }
}
17

1,递归解决

判断二叉树是否是对称,需要从子节点开始比较,两个子节点的值必须相同,并且左子节点的右子节点(如果有)必须等于右子节点的左子节点,左子节点的左子节点必须等于右子节点的右子节点。就像下面图中那样
image.png

public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true;
    //从两个子节点开始判断
    return isSymmetricHelper(root.left, root.right);
}

public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
    //如果左右子节点都为空,说明当前节点是叶子节点,返回true
    if (left == null && right == null)
        return true;
    //如果当前节点只有一个子节点或者有两个子节点,但两个子节点的值不相同,直接返回false
    if (left == null || right == null || left.val != right.val)
        return false;
    //然后左子节点的左子节点和右子节点的右子节点比较,左子节点的右子节点和右子节点的左子节点比较
    return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
}

看下运行结果
image.png


2,非递归解决

非递归解决和上面原理一样,直接看下代码,不懂的代码中有详细的注释

public boolean isSymmetric(TreeNode root) {
    //队列
    Queue<TreeNode> queue = new LinkedList<>();
    if (root == null)
        return true;
    //左子节点和右子节点同时入队
    queue.add(root.left);
    queue.add(root.right);
    //如果队列不为空就继续循环
    while (!queue.isEmpty()) {
        //每两个出队
        TreeNode left = queue.poll(), right = queue.poll();
        //如果都为空继续循环
        if (left == null && right == null)
            continue;
        //如果一个为空一个不为空,说明不是对称的,直接返回false
        if (left == null ^ right == null)
            return false;
        //如果这两个值不相同,也不是对称的,直接返回false
        if (left.val != right.val)
            return false;
        //这里要记住入队的顺序,他会每两个两个的出队。
        //左子节点的左子节点和右子节点的右子节点同时
        //入队,因为他俩会同时比较。
        //左子节点的右子节点和右子节点的左子节点同时入队,
        //因为他俩会同时比较
        queue.add(left.left);
        queue.add(right.right);
        queue.add(left.right);
        queue.add(right.left);
    }
    return true;
}

看下运行结果,这种就差了很多
image.png


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

6

return isMirror(root, root);
可以直接写return isMirror(root.left, root.right);

3

对称二叉树,C++递归写法:

    /*
        两个树互为镜像的条件:
            1、它们的两个根结点具有相同的值
            2、每棵树的右子树都与另一棵树的左子树镜像对称
    */
    bool isSymmetric(TreeNode* root) {
        return check(root, root);   // 传两个根结点,一个往左遍历,一个往右遍历
    }

    bool check(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) {         // 两棵树同为空,则默认表示这颗空树对称
            return true;
        }

        // 因为有了上面的判断,所以下面这个判断不会出现两棵树都为空的情况
        if (left == nullptr || right == nullptr || left->val != right->val) {             // 左右子树有一棵为空,则不对称,或者左右两棵子树根结点的值不一样,则不对称
            return false;
        }

        // 判断左边这棵树的左子树是否与右边这棵树的右子树对称
        // 判断左边这棵树的右子树是否与右边这棵树的左子树对称
        return check(left->left, right->right) && check(left->right, right->left); 
    }

对称二叉树,C++非递归写法:

    bool isSymmetric(TreeNode* root) {
        return check(root, root);       // 传两个根结点,一个往左遍历,一个往右遍历
    }

    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 == nullptr && Right == nullptr) continue;      // 左边的树和右边的树都为空则继续执行,因为有可能是叶结点

            // 左右两边的树有一边为空则整棵树不对称,或者左右两边的树的根结点值不一样也不对称
            if ((Left == nullptr || Right == nullptr) || (Left->val != Right->val)) {
                return false;
            }

            // 判断左边这棵树的左子树是否与右边这棵树的右子树对称
            q.push(Left->left);
            q.push(Right->right);

            // 判断左边这棵树的右子树是否与右边这棵树的左子树对称
            q.push(Left->right);
            q.push(Right->left);

        }
        return true;
    }
1

当然之前要先判断root == null 直接返回 return;原文的写法root为空时还要调用一次子函数。

1

左子树的左右分别与右子树的右左比较

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return ifSymm(root->left, root->right);
    }

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

Java递归

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

        return isSymmetricHelper(left.left, right.right)&&isSymmetricHelper(left.right, right.left);
    }

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

Java迭代

public boolean isSymmetric(TreeNode root) {
        if(root==null)
           return true;
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        q1.add(root.left);
        q1.add(root.right);
        while(!q1.isEmpty()){
            TreeNode t1 = q1.poll();
            TreeNode t2 = q1.poll();
            if(t1==null&&t2==null)
               continue;
            if(t1==null||t2==null||t1.val!=t2.val)
               return false;
            q1.add(t1.left);
            q1.add(t2.right);
            q1.add(t1.right);
            q1.add(t2.left);
        }
        return true;
    }

非递归,二叉树层次遍历

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        queue = []
        if root is None:
            return True
        queue.append(root)
        while queue:
            n = len(queue)
            res = []
            for i in range(n):
                root = queue.pop(0)
                if root == '!':
                    res.append('!')
                    continue
                res.append(root.val)
                if root.left:
                    queue.append(root.left)
                else:
                    queue.append('!')
                if root.right:
                    queue.append(root.right)
                else:
                    queue.append('!')
            if res != res[::-1]:
                return False
        return True

妙啊

root = null 就报错了