您好,登錄后才能下訂單哦!
如何分析python中的對稱二叉樹,針對這個(gè)問題,這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答,希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。
給定一個(gè)二叉樹,檢查它是否是鏡像對稱的。
例如,二叉樹 [1,2,2,3,4,4,3] 是對稱的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面這個(gè) [1,2,2,null,3,null,3] 則不是鏡像對稱的:
1
/ \
2 2
\ \
3 3
來源:力扣(LeetCode)鏈接:https://leetcode-cn.com/problems/symmetric-tree/submissions/
# 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
"""
判斷二叉樹是否對稱,先看看下面代碼是否正確,它實(shí)現(xiàn)的什么功能?
首先看遞歸基,分三種情況:
val
不相等,返回False遞歸方程如下,判斷左、右子樹都對稱。
self.isSymmetric(root.left) and self.isSymmetric(root.right)
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
if not root.left and not root.right:
return True
return root.left == root.right and self.isSymmetric(root.left) and self.isSymmetric(root.right)
以上代碼認(rèn)為下面的二叉樹才是對稱的:
這與題目要求的對稱二叉樹明顯不同,這樣才是真的對稱二叉樹:
錯(cuò)誤代碼錯(cuò)誤的原因在于遞歸方程有問題。請看下圖:
因此,得到正確的遞歸方程:
sub(left.left,right.right) and sub(left.right,right.left)
完整代碼:
class Solution(object):
def isSymmetric(self, root):
if not root:
return True
def sub(left,right):
# 沒有左和右,返回True
if not left and not right:
return True
# 沒有左或沒有右,返回False
if not left or not right:
return False
return left.val == right.val and sub(left.left,right.right) and sub(left.right,right.left)
return sub(root.left,root.right)
關(guān)于如何分析python中的對稱二叉樹問題的解答就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。