您好,登錄后才能下訂單哦!
這篇文章主要介紹了python中遍歷樹(shù)的方法有哪些,具有一定借鑒價(jià)值,需要的朋友可以參考下。希望大家閱讀完這篇文章后大有收獲。下面讓小編帶著大家一起了解一下。
各種遍歷順序如下圖所示:
樹(shù)的最大深度
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def maxdepth(self, root): if root is None: return 0 return max(self.maxdepth(root.left), self.maxdepth(root.right))+1
深度優(yōu)先
深度優(yōu)先遍歷有三種方式:前序遍歷、中序遍歷和后序遍歷
所說(shuō)的前序、中序、后序,是指根節(jié)點(diǎn)的先后順序。
前序遍歷:根節(jié)點(diǎn) -> 左子樹(shù) -> 右子樹(shù)
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def preorder(self, root): if root is None: return '' print root.val if root.lef: self.preorder(root.left) if root.right: self.preorder(root.right)
中序遍歷:左子樹(shù) -> 根節(jié)點(diǎn) -> 右子樹(shù)
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def midorder(self, root): if root is None: return '' if root.lef: self.midorder(root.left) print root.val if root.right: self.midorder(root.right)
后序遍歷:左子樹(shù) -> 右子樹(shù) -> 根節(jié)點(diǎn)
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def endorder(self, root): if root is None: return '' if root.lef: self.endorder(root.left) if root.right: self.endorder(root.right) print root.val
廣度優(yōu)先
廣度優(yōu)先遍歷,即層次遍歷,優(yōu)先遍歷兄弟節(jié)點(diǎn)
層次遍歷:根節(jié)點(diǎn) -> 左節(jié)點(diǎn) -> 右節(jié)點(diǎn)
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def graorder(self, root): if root is None: return '' queue = [root] while queue: res = [] for item in queue: print item.val, if item.left: res.append(item.left) if item.right: res.apppend(item.right) queue = res
比較兩棵樹(shù)是否相同
# class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def issame(self, root1, root2): if root1 is None and root2 is None: return True elif root1 and root2: return root1.val==root2.val and issame(root1.left, root2.left) and issame(root1.right, root2.right) else: return False
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享python中遍歷樹(shù)的方法有哪些內(nèi)容對(duì)大家有幫助,同時(shí)也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,遇到問(wèn)題就找億速云,詳細(xì)的解決方法等著你來(lái)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。