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

Question

This is an algorithm about pruning binary Tree. For example:

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

I already have a recursive method to deal with this problem, which is

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

But I also have another way to deal with this problem, which is also using postorder to cut the leave one by one.

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

If I change the code in [1] to node.val = 88, it works. Each place needs to cut will become 88. But when I am using node = None. It doesn't work. The tree will still be the original one. How did this come up? How to fix it. Thank you to anyone can help me.

Answer 1

In fact, your recursive method also used postorder's idea. It's kind like the same idea but you try to implement it with different ways. Your main problem is like what jasonharper said. For example:

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

a will still be [[1], [2]], but remember, list is not an immutable object. Therefore, if you code like this:

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

a will then be [[1, 1], [2, 1]]. This is why your node.val may change the value but not node.