专栏首页爱写BugLeetCode 101: 对称二叉树 Symmetric Tree

LeetCode 101: 对称二叉树 Symmetric Tree

题目:

给定一个二叉树,检查它是否是镜像对称的。

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题,会很加分。

Note: Bonus points if you could solve it both recursively and iteratively.

解题思路:

很简单的题, 深度优先的话同时遍历二叉树的左右子结点稍加判断即可; 广度优先的话, 一次按镜像对称从两边遍历二叉树, 一次同时取出来两个结点稍加判断即可. 这里列举两种最好的解法, 复杂度相同

深度优先递归解法:

Java:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) // 根结点为空直接返回 真
            return true;
        return isSymmetricHelper(root.left, root.right); // 辅助函数传入根结点的左右子结点
    }

    private boolean isSymmetricHelper(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) // 两结点均为空时也满足镜像对称的条件, 返回为真
            return true;
        if (node1 == null || node2 == null) // 两结点只有一个为空, 则不满足对称条件, 返回值为假
            return false;
        // 当两结点值相等, 所有子结点均满足对称条件时, 返回为真, 否则返回为假
        return (node1.val == node2.val) && isSymmetricHelper(node1.left, node2.right) && isSymmetricHelper(node1.right, node2.left);
    }
}

Python:

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: # 根结点为空直接返回 真
            return True
        return self.isSymmetricHelper(root.left, root.right) # 辅助函数传入根结点的左右子结点

    def isSymmetricHelper(self, node1: TreeNode, node2: TreeNode) -> bool:
        if not node1 and not node2: # 两结点均为空时也满足镜像对称的条件, 返回为真
            return True
        if not node1 or not node2: # 两结点只有一个为空, 则不满足对称条件, 返回值为假
            return False
        # 当两结点值相等, 所有子结点均满足对称条件时, 返回为真, 否则返回为假
        return node1.val == node2.val and self.isSymmetricHelper(node1.left, node2.right) and self.isSymmetricHelper(node1.right, node2.left)

广度优先迭代解法:

Java:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) // 根结点为空直接返回 真
            return true;
        Queue<TreeNode> queue = new LinkedList<>(); // 维护一个队列, 从左右子结点同时入队维护
        queue.add(root.left);
        queue.add(root.right);
        int size;
        TreeNode node1, node2;
        while (!queue.isEmpty()) {
            node1 = queue.poll();
            node2 = queue.poll();
            if (node1 == null && node2 == null) // 两结点均为空时也满足镜像对称的条件, 跳过该层循环
                continue;
            if (node1 == null || node2 == null) // 两结点只有一个为空, 则不满足对称条件, 返回值为假
                return false;
            if (node1.val != node2.val) // 两结点值不相等时, 返回为假
                return false;
            // 按镜像对称条件, 依次入队
            queue.add(node1.left);
            queue.add(node2.right);
            queue.add(node1.right);
            queue.add(node2.left);
        }
        return true;
    }
}

Python:

class Solution:
    def isSymmetric(self, root):
        if not root: #  根结点为空直接返回 真
            return True
        queue = collections.deque() # 维护一个队列, 从左右子结点同时入队维护
        queue.append(root.left)
        queue.append(root.right)
        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()
            if node1 == None and node2 == None: # 两结点均为空时也满足镜像对称的条件, 跳过该层循环
                continue
            if node1 == None or node2 == None: # 两结点只有一个为空, 则不满足对称条件, 返回值为假
                return False
            if node1.val != node2.val: # 两结点值不相等时, 返回为假
                return False
            # 按镜像对称条件, 依次入队
            queue.append(node1.left)
            queue.append(node2.right)
            queue.append(node1.right)
            queue.append(node2.left)
        return True

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 167:两数之和 II - 输入有序数组 Two Sum II - Input array is sorted

    函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

    爱写bug
  • LeetCode 167:两数之和 II - 输入有序数组 Two Sum II - Input array is sorted

    函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。

    爱写bug
  • LeetCode 106: 从中序与后序遍历序列构造二叉树

    Given inorder and postorder traversal of a tree, construct the binary tree.

    爱写bug
  • 初学Hadoop:mapreduce的一些理解

    MapReduce是一种编程模型,编写很少的代码就可以实现很强大的计算功能。它主要体现了分治思想,就是把一个大问题分成相同的一些小问题,最后将小问题的结果汇总起...

    heasy3
  • JavaEE基础(05):过滤器、监听器、拦截器,应用详解

    知了一笑
  • 乘积求和及符合某个条件的乘积求和

    如何得到两个数组的乘积求和呢??案例如下: ? 已知每个地市的销售单价和销售数量,需要知道整个表的销售总金额,怎么做??? 普通青年做法: ? 小编客观公正...

    用户1332619
  • DDL-脏数据层的实现

    首先说一下为什么操作不能保证原子性就会危险,因为这时就很有可能出现同时修改的情况,最终的结果极有可能并不是你所希望的(除非这些操作都是幂等性,但这种情况应该比较...

    健程之道
  • Spring 事务管理(13)

    事务管理用来确保数据的完整性和一致性。事务就是一系列的工作,它们被当做一个单独的工作单元,这些动作要么全部完成,要么全部不起作用。

    桑鱼
  • 记一次Linux修改MySQL配置不生效的问题

    自己手上有一个项目服务用的是AWS EC2,最近从安全性和性能方面考虑,最近打算把原来腾讯云的MySQL数据库迁移到AWS RDS上,因为AWS的出口规则和安全...

    phoenix.xiao
  • 工厂设计模式

    定义一个用于创建对象的接口,让子类决定实例化哪一个类,FactoryMethod使得一个类的实例化延迟到子类

    许喜朝

扫码关注云+社区

领取腾讯云代金券