剑指Offer(五十八):对称的二叉树

2018年1月26日11:02:40 4 1,972 °C
摘要

请实现一个函数,用来判断一颗二叉树是不是对称的。

剑指Offer(五十八):对称的二叉树

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

1、思路

剑指Offer(五十八):对称的二叉树

我们通常有三种不同的二叉树遍历算法,即前序遍历、中序遍历和后序遍历。在这三种遍历算法中,都是先遍历左子结点再遍历右子结点。以前序遍历为例,我们可以定义一个遍历算法,先遍历右子结点再遍历左子结点,暂且称其为前序遍历的对称遍历。

遍历第一棵树,前序遍历的遍历序列为{8,6,5,7,6,7,5},其对称遍历的遍历序列为{8,6,5,7,6,7,5}。

遍历第二颗树,前序遍历的遍历序列为{8,6,5,7,9,7,5},其对称遍历的遍历序列为{8,9,5,7,6,7,5}。

可以看到,使用此方法可以区分前两棵树,第一棵树为对称树,第二颗树不是对称树。但是当使用此方法,你会发现第三颗树的前序遍历和对称前序遍历的遍历序列是一样的。

怎么区分第三颗树呢?解决办法就是我们也要考虑NULL指针。此时,前序遍历的遍历序列{7,7,7,NULL,NULL,7,NULL,NULL,7,7,NLL,NULL,NULL},其对称遍历的遍历序列为{7,7,NULL,7,NULL,NULL,7,7,NULL,NULL,7,NULL,NULL}。因为两种遍历的序列不同,因此这棵树不是对称树。

2、代码

C++

Python:

感谢@小小毛提供python代码记本地测试用例。

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:4   其中:访客  3   博主  1

    • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

      思路是,求解它的镜像树,然后判断它们是否相等。相等则为平衡二叉树,不相等就不是。

      • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

        就把代码写到这里,还可以回过头看。python版
        # -*- coding:utf-8 -*-
        class TreeNode:
        def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        class Solution:
        def isSymmetrical(self, pRoot):
        # write code here
        if not pRoot:
        return True
        return self.recursiveTree(pRoot.left, pRoot.right)

        def recursiveTree(self, left, right):
        if not left and not right:
        return True
        if not left or not right:
        return False
        if left.val == right.val:
        return self.recursiveTree(left.left, right.right) and self.recursiveTree(left.right, right.left)
        return False
        if __name__==’__main__’:

        A1 = TreeNode(1)
        A2 = TreeNode(2)
        A3 = TreeNode(2)
        A4 = TreeNode(3)
        A5 = TreeNode(4)
        A6 = TreeNode(4)
        A7 = TreeNode(3)

        A1.left=A2
        A1.right=A3
        A2.left=A4
        A2.right=A5
        A3.left=A6
        A3.right=A7

        solution = Solution()
        ans=solution.isSymmetrical(A1)
        print(ans)

        • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

          欢迎各位优化代码哦

            • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_3 北京市 百度网讯科技联通节点

              @小小毛 太给力了,已经添加~