Симметричного обхода дерева в Python возвращает список

Я научился реализовывать inorder обход бинарного дерева поиска: 

def inorder(root): # root has val, left and right fields
    if root==None:
        return

    inorder(root.left)
    print(root.val)
    inorder(root.right)

Теперь проблема в том, что я не хочу выводить данные на консоль. Я хочу получить значения в списке. Я не могу найти способ заставить функцию возвращать список.

Я пытался s = [inorder(root)], но это не работает.

Итак, мой вопрос:

  1. В любом случае это можно сделать внутри функции inorder, то есть она должна возвращать список, а не просто печатать значения.

  2. Есть ли какой-то общий способ чтобы рекузивные функции возвращали структуры данных вместо того, чтобы просто выводить печать на консоль?

2 2
python algorithm data-structures recursion binary-search-tree

2 ответа:

Вы можете построить список рекурсивно. Просто добавьте возвращенный список из левого и правого деревьев вместе со значением в текущем узле.

def inorder(root):
    if root==None:
        return []

    left_list = inorder(root.left)
    right_list = inorder(root.right)
    return left_list + [val] + right_list
2

Вы можете передать список, а затем добавить к нему значения, как это - 

def inorder(root,ans): # root has val, left and right fields
    if root==None:
        return

    inorder(root.left)
    ans.append(root.val)
    inorder(root.right)
ans=[]
inorder(root,ans)
print(ans)

Отвечая на ваш второй запрос :

Передача самой структуры данных-самое простое решение. Если вы действительно хотите, чтобы функция "возвращала" выходные данные, Один из способов - это использование конкатенации списков, как предложил @Shaido, но это немного тяжелее для памяти, без необходимости создавая новый синглетный список при каждом рекурсивном вызове.

Лучшим решением было бы использование некоторого статического списка (т. е. фиксированный список, который будет объявлен только один раз). Но он не доступен непосредственно в python, потому что python предлагает сделать это, объявив его внутри класса. (хорошая дискуссия здесь )

1