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

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

这是一个关于修剪二叉树的算法。例如:

    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的时候。它不起作用。这棵树仍然是原来的那棵。这是怎么来的?如何修复它。谢谢任何可以帮助我的人。

其实你的递归方法也是用到了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.