python每日一题【剑指 Offer 28. 对称的二叉树】
admin
2024-03-25 03:26:36
0次

day25-2022.11.21

题目信息来源

作者:Krahets

链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm

来源:力扣(LeetCode)

剑指 Offer 28. 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

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

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

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

	1/ \2   2\   \3    3
输入:root = [1,2,2,3,4,4,3]
输出:true输入:root = [1,2,2,null,3,null,3]
输出:false

限制:

  • 0 <= 节点个数 <= 1000

题解:辅助栈法

遍历树的方式用的是递归,不过这里每次 pop 的时候和 append 的时候有一点设计。每次 pop 出的是一组需要镜像的节点,即前两个节点。然后判断是否镜像

  • 如果都为空,则是镜像,继续 continue
  • 只有一方为空,则不是镜像,return False
  • 都不为空,比较值:
    • 相同,则是镜像,继续 continue
    • 不同,则不是镜像,return False

continue 的情况下,需要 append 的顺序需要注意:并不是父节点下的两个子节点相同就是对的。headnode.left 应该和 tailnode.right 镜像,tailnode.left 应该和 head.right 镜像。所以 append 的时候也应该是这个顺序。看看能不能尝试递归的办法。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truestack = [root.left, root.right]while stack:headnode = stack.pop(0)tailnode = stack.pop(0)if headnode==None and tailnode==None:continueif (not headnode and tailnode) or (headnode and not tailnode):return Falseif headnode.val!=tailnode.val:return Falsestack.append(headnode.left)stack.append(tailnode.right)stack.append(headnode.right)stack.append(tailnode.left)return True

题解:递归法

递归法总是要考虑好怎么返回,这个是困扰我很久的问题了。(递归参数,终止条件,返回值,递推工作)

  • 递归参数:headnode 和 tailnode,对应关系在辅助栈方法里已经写了。
  • 终止条件和返回值:
    • 如果都为空,return True,因为它已经不能迭代了
    • 只有一方为空,则不是镜像,return False
    • 都不为空,比较值:
      • 相同,则是镜像,迭代
      • 不同,则不是镜像,return False
  • 递归和返回值:需要注意的是,除了初始的 root.right 和 root.left 。其他都应该是两组的比较,两个都 True,才是 True。这个也是我一直写不出来的地方。
class Solution:def isSymmetric(self, root: TreeNode) -> bool:def check(headnode, tailnode):if not headnode and not tailnode:return Trueif not headnode or not tailnode or (headnode.val!=tailnode.val):return Falsereturn check(headnode.left, tailnode.right) and check(headnode.right, tailnode.left)return not root or check(root.left, root.right)

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...