Python - лучший способ рекурсивного создания списка? - PullRequest
Новая
       9

Python - лучший способ рекурсивного создания списка?

0 голосов
/ 25 апреля 2018 
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None      

sum = 25
  ans = []
  def recurse(s, traverse, ls):
                #append tuple
                ls = ls + (traverse.val,)
                if (traverse.right):
                    recurse(s, traverse.right, ls)
                if (traverse.left):
                    recurse(s, traverse.left, ls)
                if (s==sum): 
                    #convert touple and add to answer
                    tmp = list(ls)
                    ans.append(tmp)

  a = tuple()
  recurse(0, root, a)

В этом коде я динамически добавляю списки в список (ans).В этом примере я использую рекурсию и кортежи для создания каждого подсписка, потому что он неизменен.Затем я преобразовываю его в список и добавляю к своему ответу.Если бы я использовал только списки, я не смог бы передавать копии каждый раз, когда вызывается моя функция.

Есть ли какие-либо недостатки в производительности при использовании кортежей таким образом?Есть ли лучший способ рекурсивного создания списка для похожих проблем?

Кроме того, этот метод на самом деле не будет работать с 2D-списком ... Какой лучший способ создать 2D-неизменяемый список?

1 Ответ

0 голосов
/ 25 апреля 2018

Полагаю, sum - это максимальное число обходов, которое вы хотите выполнить.

Следующие действия помогут вам: 

def traverse(root, limit=None, count=0):
    if not root or count == limit:
        return []
    traversal = [root.val]
    traversal += traverse(root.right, limit, count + len(traversal))
    traversal += traverse(root.left, limit, count + len(traversal))
    return traversal

Тогда вам нужно просто позвонитьэто выглядит так: 

root = TreeNode(20)
root.right = TreeNode(40)
root.right.right = TreeNode(50)
root.right.left = TreeNode(30)
root.left = TreeNode(10)
root.left.left = TreeNode(5)

traverse(root)          // [20, 40, 50, 30, 10, 5]
traverse(root, limit=1) // [20]
traverse(root, limit=4) // [20, 40, 50, 30]

Или, если вы можете предоставить узлы right и left на __init__, вы можете использовать классный подход функционального стиля: 

print(
    traverse(
        Node(20,
            right=Node(40,
                right=Node(50),
                left=Node(30)),
            left=Node(10,
                left=Node(5))),
        limit=3))
 # > [20, 40, 50]
...