Python對稱的二叉樹多種思路實(shí)現(xiàn)方法
對稱二叉樹的含義非常容易理解,左右子樹關(guān)于根節(jié)點(diǎn)對稱,具體來講,對于一顆對稱二叉樹的每一顆子樹,以穿過根節(jié)點(diǎn)的直線為對稱軸,左邊子樹的左節(jié)點(diǎn)=右邊子樹的右節(jié)點(diǎn),左邊子樹的右節(jié)點(diǎn)=左邊子樹的左節(jié)點(diǎn)。所以對稱二叉樹的定義是針對一棵樹,而判斷的操作是針對節(jié)點(diǎn),這時(shí)可以采取由上到下的順序,從根節(jié)點(diǎn)依次向下判斷,只需要重復(fù)調(diào)用函數(shù),不需要回溯。
題目:對稱的二叉樹題:
請實(shí)現(xiàn)一個(gè)函數(shù),用來判斷一顆二叉樹是不是對稱的。注意,如果一個(gè)二叉樹同此二叉樹的鏡像是同樣的,定義其為對稱的
解題思路一:先遍歷右子節(jié)點(diǎn)再遍歷左子節(jié)點(diǎn)。注意,我們必須把遍歷二叉樹時(shí)遇到的空指針考慮進(jìn)來。
class Solution: def isSymmetrical(self, pRoot): # write code here return self.isSymmetricalCore(pRoot,pRoot) def isSymmetricalCore(self,pRoot1,pRoot2): if not pRoot1 and not pRoot2: return True if not pRoot1 or not pRoot2: return False if pRoot1.val != pRoot2.val: return False return self.isSymmetricalCore(pRoot1.left,pRoot2.right) and self.isSymmetricalCore(pRoot1.right,pRoot2.left)
解題思路二:迭代
def isSymmetric(self, root: 'TreeNode') -> 'bool': stack = root and [(root.left, root.right)] while stack: p1, p2 = stack.pop() if not p1 and not p2: continue if not p1 or not p2: return False if p1.val != p2.val: return False stack.append((p1.left, p2.right)) stack.append((p1.right, p2.left)) return True
到此這篇關(guān)于Python對稱的二叉樹多種思路實(shí)現(xiàn)方法的文章就介紹到這了,更多相關(guān)Python對稱的二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
pytorch中關(guān)于distributedsampler函數(shù)的使用
這篇文章主要介紹了pytorch中關(guān)于distributedsampler函數(shù)的使用,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-02-02python實(shí)現(xiàn)有序遍歷dict(字典)
這篇文章主要介紹了python實(shí)現(xiàn)有序遍歷dict(字典),具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08Python中NameError: name ‘Image‘ is not&nb
本文主要介紹了Python中NameError: name ‘Image‘ is not defined的問題解決,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06Python二次規(guī)劃和線性規(guī)劃使用實(shí)例
這篇文章主要介紹了Python二次規(guī)劃和線性規(guī)劃使用實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12Python基礎(chǔ)學(xué)習(xí)之模塊的安裝和卸載
其實(shí)現(xiàn)在還是有很多剛開始學(xué)習(xí)的小伙伴,會(huì)遇到模塊不會(huì)安裝的情況,或者一遇到報(bào)錯(cuò)就懵了,這樣就很耽誤我們的學(xué)習(xí)進(jìn)度。所以,今天我們就來了解一下Python幾種安裝模塊的方法吧2022-09-09Python使用pptx實(shí)現(xiàn)復(fù)制頁面到其他PPT中
這篇文章主要為大家詳細(xì)介紹了python如何使用pptx庫實(shí)現(xiàn)從一個(gè)ppt復(fù)制頁面到另一個(gè)ppt里面,文中的示例代碼講解詳細(xì),感興趣的可以嘗試一下2023-02-02