python - 理解BST、Python中序遍历的逻辑

Question

我正在学习编码面试和使用许多不同的数据结构。

我对树问题比较陌生，每天都在做问题来练习。

记住公式是一回事，真正理解它们又是另一回事。当我理解某事时，很容易将这种理解应用到更困难的问题上。

递归解决方案对我来说有点难以想象，虽然从直觉上它们是有道理的，但我正试图深入了解堆栈上发生的事情。

我有一棵树，想按顺序遍历。没问题。

data = [] 

def checkBST(root):
    if root:
        checkBST(root.left)
        data.append(root.data)
        checkBST(root.right)
    print(data)   

我创建了数据变量来打印出每次通过该方法时存储的内容。

打印出来

[]
[1]
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]

我试图从逻辑上看正在发生的事情，并想知道我的逻辑是否正确。

有15个打印结果和7个节点。然而，我们得到 15 个，因为有 8 个地方检查了节点，其中节点为 None。这发生在节点 1、3、5、7 上。

我们正在检查树的左半部分，然后再检查右半部分。

[] 
#nothing stored because we move onto Node 2 as we don't hit the base case.
[1] 
#1 stored because Node 1 doesn't have a left value. So we move onto the append call. 
[1] 
#1 returned because Node 1 doesn't have a right value.
[1, 2] 
#2 stored because because we finished checking the left side and moved onto append data.
[1, 2, 3] 
#3 is stored because we are calling the in order traversal on the right side of two now. 
[1, 2, 3]
#3 is returned again because it doesn't have a root.left
[1, 2, 3]
#3 is returned again because it doesn't have a root.right
[1, 2, 3, 4]
# we hit the append method for 4, now we move onto the in order traversal on the right
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]

右侧将像左侧一样被检查，所以我没有写我的逻辑，因为它是多余的。

如果我以正确的格式查看此问题，我只想澄清一下。

感谢您帮助理解这一点!

Answer 1

输出中的注释并不总是正确的。

第一个输出 ([]) 在函数调用结束时发生。发生这种情况的第一次调用是当 root 是节点 1 时，从那里进行第一次递归调用。该调用将以 None 作为参数，因此这是第一次调用到达 print 语句。

所以我们有这些正在进行的电话:

 checkBST(4)
     checkBST(2) # left child of 4
         checkBST(1) # left child of 2
             checkBST(None) # left child of 1
                 print # --> []

当最深调用完成时，节点为 1 的函数会将 1 添加到数据列表中，然后对右 child 进行递归调用，也就是 None 和 [1 ] 被打印出来。

这是该过程的可视化。列表示递归的深度，行表示随着时间的推移(向下)发生的事件序列。最后一列保留用于显示 data 的当前值。当它有黄色背景时，表示它已打印。

浅蓝色表示代码在该递归深度执行。深蓝色表示相应的函数调用正在等待(在堆栈上)，等待嵌套递归调用返回。

从这张图片中，您还可以看出为什么有时会重复相同的输出:当算法回溯时，它会在不同的递归级别打印。