代码之家  ›  专栏  ›  技术社区  ›  codingBoy

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

  •  1
  • codingBoy  · 技术社区  · 6 年前

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

        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 .它不起作用。这棵树仍将是原来的树。这是怎么发生的?如何修复它。谢谢所有能帮助我的人。

    1 回复  |  直到 6 年前
        1
  •  1
  •   Heaven    6 年前

    事实上,您的递归方法也使用了postorder的思想。这有点像同一个想法,但你尝试用不同的方式来实现它。 你的主要问题就像jasonharper说的那样。 例如:

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

    a仍然是 [[1], [2]] ,但请记住,list不是一个不变的对象。 因此,如果您这样编码:

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

    然后,a将是[[1,1],[2,1]]。这就是为什么你 node.val 可能会更改值,但不会 node