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))