字典的递归工作问题

Question

我对递归有疑问。请帮助澄清我的疑问。

我有一个存储二叉树节点的数据结构：

 class Node:
        def __init__(self, key, left=None, right=None):
            self.data = key
            self.left = left
            self.right = right
    # Recursive function to print left view of given binary tree
    def printLeftView(root,level=0,leveldic={}):
        if root==None:
            return
        print(root.data,leveldic)
        if level not in leveldic:
            leveldic[level]=root.data
            print(root.data)
        printLeftView(root.left,level+1,leveldic)
        printLeftView(root.right,level+1,leveldic)
    
"""
                      1
                    /    \
                   2       3
                  /      /    \
                4      5      6
                       \       
                        8

"""
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.right = Node(4)
    root.right.left = Node(5)
    root.right.right = Node(6)
    root.right.left.right = Node(8)
    printLeftView(root)

输出：

> 1 {}
>     1
>     2 {0: 1}
>     2
>     4 {0: 1, 1: 2}
>     4
>     3 {0: 1, 1: 2, 2: 4}
>     5 {0: 1, 1: 2, 2: 4}
>     8 {0: 1, 1: 2, 2: 4}
>     8
>     6 {0: 1, 1: 2, 2: 4, 3: 8}

疑问：

为什么字典在 returning 后没有恢复到原来的状态？

即打印 4 字典后为

{0:1, 1:2, 2:4}

并且因为它 return 并且当回到节点 3 时，它应该回到以前的状态，而 returning 变成

{0:1, 1:3}

这并没有发生，字典没有得到改变，它与节点 4 相同。

{0:1, 1:2, 2:4}

可能是什么原因？

Answer 1

似乎字典参数不是字典的副本，而是在内存中引用它，所以当它应该返回节点 3 时，它是旧键。您必须复制它。

def printLeftView(root,level=0,oldic={}):
    if root==None:
        return

    leveldic={} #making new dict
    for i in oldic:
        leveldic[i]=oldic[i] #and copying it values, to work on copy
    
    leveldic[level]=root.data
    print(root.data)
    print(root.data,leveldic)

    printLeftView(root.left,level+1,leveldic)
    printLeftView(root.right,level+1,leveldic)

Answer 2

接受的答案不正确：它会产生错误的输出。

原始代码完全按照算法的预期工作：所有递归执行上下文共享一个字典，它不应该 return从递归调用返回时回到以前的状态。如果你试图“修复”这个，你实际上会破坏算法，然后输出通常是错误的。

请注意，当您将字典对象作为参数传递给函数时，它不会被深度复制：函数将在新变量中获取参数，但它仍然是同一个字典。除非一个新值被赋值给那个变量，任何对这个字典的突变都将是那个单一字典实例。

但是您的代码还有另一个问题：默认参数值 leveldic={} 有问题。这个赋值只发生一次，这是 Python 特有的行为。这意味着如果您从主程序再次调用，您将仍然继续使用上次调用后的字典对象。

如果进行第二次调用，您将需要重置它：

def printLeftView(root, level=0, leveldic=None):
    if leveldic is None:
        leveldic = {}
    if root is None:
        return
    if level not in leveldic:
        leveldic[level] = root.data
        print(root.data)
    printLeftView(root.left, level + 1, leveldic)
    printLeftView(root.right, level + 1, leveldic)

字典的递归工作问题

Recursion Working problem with dictionary

python

tree

recursion

binary-tree