使用 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

其实你的递归方法也是用到了postorder的思想。这有点像同一个想法，但你尝试用不同的方式来实现它。您的主要问题就像 jasonharper 所说的那样。例如：

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.

使用 python[postorder 方法不起作用] 的二叉树修剪

Binary Tree Pruning using python[postorder method doesn't work]

python

python-3.x

algorithm

binary-tree

inorder