溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
請寫一個程序創建一棵二叉樹，并按照一定規則，輸出二叉樹根節點到葉子節點的路徑。
規則如下：
1、從最頂端的根結點，到最下面的葉子節點，計算路徑通過的所有節點的和，如果與設置的某一值的相同，那么輸出這條路徑上的所有節點。
2、從根節點遍歷樹時，請請按照左到右遍歷，即優先訪問左子樹的節點。
二叉樹創建規則：從上到下一層一層的，按照從左到右的順序進行構造
輸入"10,5,12,4,7"值，構造的樹如下：
1） 10
2） 10
/
5
3） 10
/\
5 12
4） 10
/\
5 12
/
4
5） 10
/\
5 12
/\
4 7
針對上面的二叉樹，如果當前我們設置的“路徑和”為19，那么輸出結果為:
10,5,4
如果有多個路徑，按到左到右的順序遍歷生成的結果每行顯示一個顯示。例如如果當前我們設置的“路徑和”為22，那么
輸出結果為:
10,5,7
10,12
如果沒有找到路徑和為設置的值的路徑，輸出error。
三、輸入:
輸入整數N---路徑和
一行字符串，多個正整數，之間用","隔開
四、輸出: 滿足條件的二叉樹路徑
五、樣例輸入:
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 = [] # 依次存放左右孩子未滿的節點
def __init__(self):
self.root = None
def add(self, number):
node = Node(number) # 將輸入的數字節點化，使其具有左右孩子的屬性
if self.root == None:
self.root = node
Tree.lt.append(self.root)
else:
while True:
point = Tree.lt[0] # 依次對左右孩子未滿的節點分配孩子
if point.left ==None:
point.left = node
Tree.lt.append(point.left) # 該節點后面作為父節點也是未滿的，也要加入到列表中。
return
elif point.right ==None:
point.right = node
Tree.lt.append(point.right) # 與左孩子同理
Tree.lt.pop(0) # 表示該節點已擁有左右孩子，從未滿列表中去除
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))
輸出樣例：
總結
以上所述是小編給大家介紹的python3實現在二叉樹中找出和為某一值的所有路徑，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對億速云網站的支持！
如果你覺得本文對你有幫助，歡迎轉載，煩請注明出處，謝謝！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
