二叉树获取每个级别的所有节点

Question

我正在尝试解决以下问题，假设我有这个二叉树...

然后我需要获取每个级别的所有节点，所以我的结果将是...

[[3],[9,20],[15,7]]

我相信我正在接近解决方案，但我不确定我哪里出错了，如果有人可以帮助我解决我的问题那会很棒，如果我在错误的轨道上，请让我知道。

我的第一步是使用以下函数获取树的深度...

def get_depth(self, root):
    if root.left == None and root.right == None:
        return 1
    return max(self.get_depth(root.left), self.get_depth(root.right)) + 1

深度为3。

接下来我调用了一个旨在给我预期结果的函数...

def levelOrder(self, root):
    depth = self.get_depth(root)
    return self.find_comb(root, [[]]*depth, 0)

def find_comb(self, root, result, level):
    if root is None:
        return None
    self.find_comb(root.left, result, level+1)
    self.find_comb(root.right, result, level+1)
    result[level].append(root.val)
    return result

我的想法是，我会递归遍历树，level 参数会跟踪我所在的当前级别。然后我会将该级别上的所有 root.val 附加到该索引处的结果。

所以假设我在级别 1（我们从 0 开始），那么级别 1 的节点是 9 和 20。所以结果看起来像 [[], [9, 20], [], []]，它会对树的每一层都这样做。我希望我的逻辑很清楚。相反，我得到的结果是...

[[9, 15, 7, 20, 3], [9, 15, 7, 20, 3], [9, 15, 7, 20, 3]]

Answer 1

我不知道 Phyton，但你可能想看看 Phyton 上的 BFS 实现。

https://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

Answer 2

其实你不需要求树的深度。您只需遍历树，同时保持您所在的级别，比方说在 level 变量中。并在 listOfLists[level] 处插入您的值。当然你必须处理IndexError: list index out of range。这是一个简单的实现：

def levelTraversal(root, level):
    if root is None:
        return

    if level >= len(listOfLists):
        list = []
        listOfLists.append(list)
    listOfLists[level].append(root.v)
    levelTraversal(root.l, level+1)
    levelTraversal(root.r, level+1)

这样称呼它：levelTraversal(rootNode, 0)

对于你的树，结果是：[[3], [9, 20], [15, 7]]

二叉树获取每个级别的所有节点

Binary tree get all nodes for every level

python

algorithm

tree

recursion

binary-tree