专栏首页爱写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][python]Symmetric Tree/对称二叉树

    其中左子树和右子树对称的条件: 两个节点值相等,或者都为空 左节点的左子树和右节点的右子树对称 左节点的右子树和右节点的左子树对称

    蛮三刀酱
  • LeetCode-101.对称二叉树

    链接:https://leetcode-cn.com/problems/symmetric-tree/description/ 给定一个二叉树,检查它是否是它自...

    张诺谦
  • Leetcode 101. 对称二叉树

    以 t1、t2 表示二叉树的左子树和右子树,若 t1 与 t2 对称,则二叉树对称;若 t1 的根节点值与 t2 的根节点值相等,且 t1 的左子树与 t2 的...

    zhipingChen
  • 【Leetcode】101. 对称二叉树

    入队顺序依次是, 左子树的左儿子,右子树的右儿子 左子树的右儿子,右子树左右儿子。 这样出队的时候两两检查是不是对称。

    Leetcode名企之路
  • LeetCode 101.对称二叉树 - JavaScript

    心谭博客
  • Leetcode No.101 对称二叉树

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

    week
  • LeetCode 100 及 101题

    输入: 1 1 / \ 2 2...

    Carlos Ouyang
  • Leetcode|二叉树的属性|101. 对称二叉树

    SL_World
  • [LeetCode] Symmetric Tree

    1、题目名称 Symmetric Tree https://leetcode.com/problems/symmetric-tree/ 2、题目内容 Give...

    程序员小王
  • 101 对称二叉树

    我们先来划分子问题,一个树对称也就最终根节点的左子树与右子树是对称的镜像的,那么要求左子节点与右子节点相等的同时左节点的左子树(右子树)与右节点的右子树(左子树...

    木瓜煲鸡脚
  • 101. 对称二叉树

    杨鹏伟
  • 101. 对称二叉树

    Michel_Rolle
  • 101. 对称二叉树

    递归: 只有根节点的值是比较两个儿子节点的值,其他结点都是左节点的左孩子和右节点的右孩子,右节点的左孩子和左节点的右孩子比较,因此这里搞了两级比较;

    名字是乱打的
  • 二叉树问题(一)-LeetCode 110、617、101、814、655、98、654(递归思路)

    给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1

    算法工程师之路
  • Leetcode-Easy 101. Symmetric Tree

    101. Symmetric Tree 描述: 判断一个颗二叉树是否左右对称 ? 思路: 将二叉树的左右节点对放在的队列里,然后出队,判断节...

    致Great
  • [Leetcode][二叉树]相关题目汇总/分析/总结

    前中后三种序列,递归都是一样的理解。迭代的话,前后两个可以互相理解。中序需要单独理解。当然我认为可能我还没有理解透彻。

    蛮三刀酱
  • 【关关的刷题日记57】Leetcode 101. Symmetric Tree

    关关的刷题日记57 – Leetcode 101. Symmetric Tree 题目 ? 题目的意思是判断一棵树是否是镜像的,此处镜像指的是中心对称的树。 思...

    WZEARW
  • DFS基础问题-LeetCode 98、101(二叉树中序遍历,层次遍历)

    假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

    算法工程师之路
  • 15 道二叉树手写算法题(三)

    Leetcode 572. Subtree of Another Tree (Easy)

    乔戈里

扫码关注云+社区

领取腾讯云代金券