如何在Python中创建一个函数，返回二进制树某个深度上的所有标记

Question

我正在努力重考Python考试，但我从未真正掌握过二进制树的窍门。在一个练习中，我必须制作一个函数，该函数以int和树为参数，并返回指定深度上每个节点标记的列表。

我有基本的

@dataclass
class Node:
mark: Any
left: Optional['Node']
right: Optional['Node']

与之合作。我知道如何确定二叉树的最大深度

def maxDepth(node:Node):
if node is None:
return -1
else :
lDepth = maxDepth(node.left)
rDepth = maxDepth(node.right)

if (lDepth > rDepth):
return lDepth+1
else:
return rDepth+1

并尝试使用while循环在某个深度处停止。

def layer(n:int,node:Node):
result=[]
depth=maxDepth(node)
while depth != n:
new_depth=maxDepth(node)
result.append(node)
return result

但我的代码毫无意义。我也想过是否可以制作一个递归深度查找函数，每次调用它都会计数，但不知道如何实现。欢迎任何帮助，我不想要直接的解决方案，但如果你能给我指明正确的方向，那就太好了：(

Answer 1

我认为这样的东西可能会有所帮助：

from typing import Any, Optional
class Node:
mark: Any
left: Optional['Node']
right: Optional['Node']
def traverse_tree(node:Node,currentDepth:int,desiredDepth:int):
if node != None:
traverse_tree(node.left,currentDepth+1,desiredDepth)
traverse_tree(node.right,currentDepth+1,desiredDepth)
if currentDepth==desiredDepth:
print(node)

您只需要从currentDepth为0开始，这段代码将遍历树，以所需的深度打印这些元素。