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

Question

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

       3
      / \
     9  20
       /  \
      15   7

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

[[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级别上的所有内容附加到该索引的结果中。

假设我在 level 上1（我们从 0 开始），那么 level 上的节点1是9和20。所以结果看起来像[[], [9, 20], [], []]，并且它会对树的每个级别执行此操作。我希望我的逻辑是清楚的。相反，我得到的结果是......

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

Answer 1

您实际上不需要找到树的深度。你只需遍历树，同时保持你所在的级别，假设是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]]