您好,登錄后才能下訂單哦!
請(qǐng)寫一個(gè)程序創(chuàng)建一棵二叉樹,并按照一定規(guī)則,輸出二叉樹根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑。
規(guī)則如下:
1、從最頂端的根結(jié)點(diǎn),到最下面的葉子節(jié)點(diǎn),計(jì)算路徑通過的所有節(jié)點(diǎn)的和,如果與設(shè)置的某一值的相同,那么輸出這條路徑上的所有節(jié)點(diǎn)。
2、從根節(jié)點(diǎn)遍歷樹時(shí),請(qǐng)請(qǐng)按照左到右遍歷,即優(yōu)先訪問左子樹的節(jié)點(diǎn)。
二叉樹創(chuàng)建規(guī)則:從上到下一層一層的,按照從左到右的順序進(jìn)行構(gòu)造
輸入"10,5,12,4,7"值,構(gòu)造的樹如下:
1) 10
2) 10
/
5
3) 10
/\
5 12
4) 10
/\
5 12
/
4
5) 10
/\
5 12
/\
4 7
針對(duì)上面的二叉樹,如果當(dāng)前我們?cè)O(shè)置的“路徑和”為19,那么輸出結(jié)果為:
10,5,4
如果有多個(gè)路徑,按到左到右的順序遍歷生成的結(jié)果每行顯示一個(gè)顯示。例如如果當(dāng)前我們?cè)O(shè)置的“路徑和”為22,那么
輸出結(jié)果為:
10,5,7
10,12
如果沒有找到路徑和為設(shè)置的值的路徑,輸出error。
三、輸入:
輸入整數(shù)N---路徑和
一行字符串,多個(gè)正整數(shù),之間用","隔開
四、輸出: 滿足條件的二叉樹路徑
五、樣例輸入:
22
10,5,12,4,7
六、樣例輸出:
10,5,7
10,12
demo:
class Node(object): def __init__(self, x): self.val = x self.left = None self.right = None class Tree(object): lt = [] # 依次存放左右孩子未滿的節(jié)點(diǎn) def __init__(self): self.root = None def add(self, number): node = Node(number) # 將輸入的數(shù)字節(jié)點(diǎn)化,使其具有左右孩子的屬性 if self.root == None: self.root = node Tree.lt.append(self.root) else: while True: point = Tree.lt[0] # 依次對(duì)左右孩子未滿的節(jié)點(diǎn)分配孩子 if point.left ==None: point.left = node Tree.lt.append(point.left) # 該節(jié)點(diǎn)后面作為父節(jié)點(diǎn)也是未滿的,也要加入到列表中。 return elif point.right ==None: point.right = node Tree.lt.append(point.right) # 與左孩子同理 Tree.lt.pop(0) # 表示該節(jié)點(diǎn)已擁有左右孩子,從未滿列表中去除 return class Solution: def __init__(self): self.results = [] def RecursionFindPath(self, root, expectNumber, result): result.append(root.val) if root.left == None and root.right == None and sum(result) == expectNumber: self.results.append(result) temp = result[:] if root.left: self.RecursionFindPath(root.left, expectNumber, result) result = temp[:] if root.right: self.RecursionFindPath(root.right, expectNumber, result) def FindPath(self, root, expectNumber): if root == None: return [] self.RecursionFindPath(root, expectNumber, []) self.results = sorted(self.results, key=len, reverse=True) return self.results if __name__ =='__main__': t = Tree() # 二叉樹類的實(shí)例化 L = [10, 5, 12, 4, 7] for i in L: t.add(i) expectNum = 22 print(Solution().FindPath(t.root, expectNum))
輸出樣例:
總結(jié)
以上所述是小編給大家介紹的python3實(shí)現(xiàn)在二叉樹中找出和為某一值的所有路徑,希望對(duì)大家有所幫助,如果大家有任何疑問請(qǐng)給我留言,小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)億速云網(wǎng)站的支持!
如果你覺得本文對(duì)你有幫助,歡迎轉(zhuǎn)載,煩請(qǐng)注明出處,謝謝!
免責(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)容。