前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 101. 对称二叉树

Leetcode 101. 对称二叉树

作者头像
zhipingChen
发布2019-05-24 09:46:39
2640
发布2019-05-24 09:46:39
举报
文章被收录于专栏:编程理解

题目描述

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

递归解法

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

代码语言:javascript
复制
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        return self.compare(root.left,root.right)
    def compare(self,node1,node2):
        if not node1 and not node2:
            return True
        if node1 and node2 and node1.val==node2.val:
            return self.compare(node1.left,node2.right) and self.compare(node1.right,node2.left)
        return False

迭代解法

以队列形式存储 t1_n 节点的右子节点与 t2_n 节点的左子节点,同时存储 t1_n 节点的左子节点与 t2_n 节点的右子节点,两两比较,节点不同则不是对称子树。

代码语言:javascript
复制
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        arr=[root,root]
        while len(arr)>0:
            node1,node2=arr.pop(0),arr.pop(0)
            if not node1 and not node1:
                continue
            if node1 and node2 and node1.val==node2.val:
                arr.append(node1.right)
                arr.append(node2.left)
                arr.append(node1.left)
                arr.append(node2.right)
            else:
                return False
        return True
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.05.23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档