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.

In for node in orderlist:, node is a variable that takes on elements of the list one by one. Assigning to it has absolutely no effect on the list, it's not an alias for a particular position in the list as you seem to expect. — jasonharper
– jasonharper, Commented Apr 25, 2018 at 3:15
Yes. You are right. I test it and that's why my program doesn't work. Thanks a lot. I am such an idiot :). — codingBoy
– codingBoy, Commented Apr 25, 2018 at 3:37

Heaven · Accepted Answer · 2018-04-25 11:51:53Z

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.

answered Apr 25, 2018 at 11:51

Heaven

5363 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related