我正在学习编码面试和使用许多不同的数据结构。
我对树问题比较陌生,每天都在做问题来练习。
记住公式是一回事,真正理解它们又是另一回事。当我理解某事时,很容易将这种理解应用到更困难的问题上。
递归解决方案对我来说有点难以想象,虽然从直觉上它们是有道理的,但我正试图深入了解堆栈上发生的事情。
我有一棵树,想按顺序遍历。没问题。
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]
右侧将像左侧一样被检查,所以我没有写我的逻辑,因为它是多余的。
如果我以正确的格式查看此问题,我只想澄清一下。
感谢您帮助理解这一点!
最佳答案
输出中的注释并不总是正确的。
第一个输出 ([]
) 在函数调用结束时发生。发生这种情况的第一次调用是当 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
的当前值。当它有黄色背景时,表示它已打印。
浅蓝色表示代码在该递归深度执行。深蓝色表示相应的函数调用正在等待(在堆栈上),等待嵌套递归调用返回。
从这张图片中,您还可以看出为什么有时会重复相同的输出:当算法回溯时,它会在不同的递归级别打印。
关于python - 理解BST、Python中序遍历的逻辑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46992970/