給定一個(gè)二叉樹智袭，并輸入一個(gè)數(shù)奔缠，找出二叉樹中從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑和與輸入值相等的路徑。
這篇放了很久了吼野，是以前寫的校哎，今天沒有新的產(chǎn)出，寫了一下午的C。
真是難為我了闷哆。
import random
class BiTNode:
def __init__(self, arg):
self.data = arg
self.left_child = None
self.right_child = None
# 構(gòu)造二叉樹
def constructBitree(x):
# x為二叉樹節(jié)點(diǎn)個(gè)數(shù)
arr=[]
for i in range(x):
arr.append(random.randint(-9, 9))
root=arrayToBiTree(arr)
return root
def arrayToBiTree(array):
#判斷arr是否為空
if len(array)==0:
return BiTNode(array[0])
mid=len(array)//2 # 有序數(shù)組的中間元素的下標(biāo)
# print(mid)
# start=0 # 數(shù)組第一個(gè)元素的下標(biāo)
# end=-1 # 數(shù)組最后一個(gè)元素的下標(biāo)
root = None
if len(array) > 0:
# 將中間元素作為二叉樹的根
root=BiTNode(array[mid])
# 如果左邊的元素個(gè)數(shù)不為零腰奋，則遞歸調(diào)用函數(shù)，生成左子樹
if len(array[:mid]) > 0:
root.left_child = arrayToBiTree(array[:mid])
# 如果右邊的元素個(gè)數(shù)不為零抱怔，則遞歸調(diào)用函數(shù)劣坊，生成左子樹
if len(array[mid+1:]) > 0:
root.right_child = arrayToBiTree(array[mid+1:])
return root
# 從此之后函數(shù)命名都應(yīng)該用下劃線分割單詞
def find_path(root, number, path, sum_path):
if root is None:
return None
# 前序遍歷，保存從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑屈留，并記錄值
sum_path = sum_path + root.data
path.append(root.data) # 將根節(jié)點(diǎn)加入列表
# 如果當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)局冰，且路徑和與輸入值相等，輸出并繼續(xù)遍歷
if (root.left_child is None and root.right_child is None) and sum_path == number:
print("存在路徑!")
print(path)
# else:
# print("不存在路徑绕沈！")
# 遍歷左子樹
if root.left_child is not None:
find_path(root.left_child, number, path, sum_path)
# 遍歷右子樹
if root.right_child is not None:
find_path(root.right_child, number, path, sum_path)
path.pop()
sum_path = sum_path - root.data
if __name__ == '__main__':
root1 = constructBitree(100)
num = int(input("請輸入一個(gè)值:\n"))
sum_path = 0 # 記錄路徑和
tree_path = [] # 用于記錄路徑
find_path(root1, num, tree_path, sum_path)
# if tree_path:
# print("存在路徑锐想！\n為：")
# else:
# print("不存在路徑！")
今天有點(diǎn)事情乍狐，而且電腦鍵盤壞了赠摇。就不多shuole.
