建站
咨詢
售后
建站咨詢
新聞中心
請寫一個程序創(chuàng)建一棵二叉樹，并按照一定規(guī)則，輸出二叉樹根節(jié)點到葉子節(jié)點的路徑。
規(guī)則如下：
1、從最頂端的根結(jié)點，到最下面的葉子節(jié)點，計算路徑通過的所有節(jié)點的和，如果與設(shè)置的某一值的相同，那么輸出這條路徑上的所有節(jié)點。
2、從根節(jié)點遍歷樹時，請請按照左到右遍歷，即優(yōu)先訪問左子樹的節(jié)點。
二叉樹創(chuàng)建規(guī)則：從上到下一層一層的，按照從左到右的順序進行構(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
針對上面的二叉樹，如果當前我們設(shè)置的“路徑和”為19，那么輸出結(jié)果為:
10,5,4
如果有多個路徑，按到左到右的順序遍歷生成的結(jié)果每行顯示一個顯示。例如如果當前我們設(shè)置的“路徑和”為22，那么
輸出結(jié)果為:
10,5,7
10,12
如果沒有找到路徑和為設(shè)置的值的路徑，輸出error。
三、輸入:
輸入整數(shù)N---路徑和
一行字符串，多個正整數(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é)點
def __init__(self):
self.root = None
def add(self, number):
node = Node(number) # 將輸入的數(shù)字節(jié)點化，使其具有左右孩子的屬性
if self.root == None:
self.root = node
Tree.lt.append(self.root)
else:
while True:
point = Tree.lt[0] # 依次對左右孩子未滿的節(jié)點分配孩子
if point.left ==None:
point.left = node
Tree.lt.append(point.left) # 該節(jié)點后面作為父節(jié)點也是未滿的，也要加入到列表中。
return
elif point.right ==None:
point.right = node
Tree.lt.append(point.right) # 與左孩子同理
Tree.lt.pop(0) # 表示該節(jié)點已擁有左右孩子，從未滿列表中去除
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() # 二叉樹類的實例化
L = [10, 5, 12, 4, 7]
for i in L:
t.add(i)
expectNum = 22
print(Solution().FindPath(t.root, expectNum))另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
本文名稱：python3實現(xiàn)在二叉樹中找出和為某一值的所有路徑(推薦)-創(chuàng)新互聯(lián)
標題URL：http://www.dlmjj.cn/article/cciohd.html
