Удаление двоичного дерева с использованием python [метод postorder не работает]

Question

Это алгоритм обрезки двоичного дерева. Например:

    1                      1
   / \                      \
  0   1          =>          1
 / \ / \                      \
0  00   1                      1

У меня уже есть рекурсивный метод для решения этой проблемы, а именно

def pruneTree_recursion(root):
    if root is None:
        return None
    root.left = pruneTree_recursion(root.left)
    root.right = pruneTree_recursion(root.right)
    return root if root.val == 1 or root.left or root.right else None

Но у меня также есть другой способ решения этой проблемы, который также использует postorder, чтобы сократить отпуск один за другим.

def pruneTree(root):
        def postorder(root, orderlist):
            if root:
                postorder(root.left, orderlist)
                postorder(root.right, orderlist)
                orderlist.append(root)
            return orderlist
        orderlist = postorder(root, [])
        for node in orderlist:
            if node.val == 0:
                if (node.left is None) and (node.right is None):
                    node = None   # May be the problem is here [1]
        return root

Если я изменю код в [1] на node.val = 88, это сработает. Каждое место, которое нужно вырезать, станет 88. Но когда я использую node = None. Не работает Дерево все равно будет оригинальным. Как это получилось? Как это исправить. Спасибо всем, кто может мне помочь.

Answer 1

На самом деле, ваш рекурсивный метод также использовал идею пост-заказа.Это похоже на ту же идею, но вы пытаетесь реализовать ее разными способами.Твоя главная проблема в том, что сказал Джейсонхарпер.Например:

a = [[1], [2]]
for list in a:
    list = []

a по-прежнему будет [[1], [2]], но помните, список не является неизменным объектом.Поэтому, если вы напишите так:

a = [[1], [2]]
for list in a:
    list.append(1)

a будет [[1, 1], [2, 1]].Вот почему ваш node.val может изменить значение, но не node.