了解BST的Inorder遍历的逻辑

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到数据表，然后进行递归调用的右孩子，这也是None和[1]被打印。

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

浅蓝色表示代码在该递归深度执行。较深的蓝色表示相应的函数调用处于挂起状态（在堆栈上），等待嵌套的递归调用返回。

从这个图片也可以看到为什么同样的输出有时重复：它是在不同的递归级别打印为算法回溯。