Блог

Здравствуйте, я пытаюсь решить следующий вопрос по leetcode, [https://leetcode.com/problems/unique-binary-search-trees-ii /].

Я знаю, что у меня есть доступ к решению, но я попытался решить проблему по-своему, и я застрял, и я хотел бы знать, разрешима ли она так, как я это делаю. Вот код:

 class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def generateTrees(myrange, n, res = None):
    if res == None:
        res = []
    if myrange == []:
        res.append(None)
        return
    for root in myrange:
        res.append(root)
        generateTrees([i for i in range(root) if i in set(myrange)], n, res) #leftchild
        generateTrees([i for i in range(root 1, n) if i in set(myrange)], n, res) #rightchild
    return res
  

Изначально myrange это просто список, содержащий значения узлов, и n это длина myrange .

То, как я это делаю, — это своего рода DFS, где я перебираю узлы, делая каждый из них корневым один раз, а затем я делаю то же самое для левого и правого поддеревьев, чтобы получить все комбинации. Но проблема, с которой я сталкиваюсь, заключается в том, что я не могу понять, как управлять res удалением элементов из него по мере возврата к моей рекурсии (и сделать так, чтобы он res содержал только допустимые bst, а затем помещал их в какой-то другой список, который будет моим фактическим результатом).

Я хотел бы получить некоторые указания или даже просто комментарии, если вы считаете, что мой подход верен или плох .. и т.д.

Проблемы:

• Как вы упомянули, ваш код создает только один список, к которому он продолжает добавляться.
• Даже если вы это исправите, списки никогда не будут отображаться в порядке, подобном BFS, что, по-видимому, предполагает пример вопроса.
• Для выбранного корня вам нужно перечислить все комбинации его возможных левых поддеревьев с его возможными правыми поддеревьями — декартово произведение, если хотите. Эта логика отсутствует в вашем коде.

Я бы:

• не передавать res в качестве аргумента рекурсивной функции. Просто верните его, и пусть вызывающий объект разбирается с ним.
• не используйте диапазоны, поскольку это только усложняет ситуацию. if i in set(myrange) Кажется неэффективным способом получить перекрытие между двумя диапазонами. Вместо этого я бы передал две крайности диапазона в качестве отдельных аргументов.
• используйте TreeNode класс для фактического создания деревьев, а затем займитесь созданием требуемого выходного формата.
• Для генерации выходного формата вам нужен BFS-переход по дереву, и это может быть реализовано как метод на TreeNode .

Вот что, я думаю, сработает:

 class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def breadth_first(self):
        lst = []
        todo = [self]
        while any(todo):
            node = todo.pop(0)
            lst.append(node.val if node else None)
            if node:
                todo.append(node.left)
                todo.append(node.right)
        return lst

def generateTrees(n):
    def recur(start, end): # end is not included
        if start >= end:
            return [None]
        trees = []
        for root in range(start, end):
            lefts = recur(start, root)
            rights = recur(root 1, end)
            # Cartesian product:
            for left in lefts:
                for right in rights:
                    # Start with a new tree, and append to result
                    tree = TreeNode(root)
                    tree.left = left
                    tree.right = right
                    trees.append(tree)
        return trees
    return recur(1, n 1)

# Create the trees as a list of TreeNode instances:
trees = generateTrees(3)
# Convert to a list of lists 
print([tree.breadth_first() for tree in trees])