二叉树获取每一层的所有节点

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”附加到结果中。例如，假设我位于第1级（我们从0开始），那么第1级上的节点为9和20。因此，结果看起来像“[[], [9, 20]，[]，[]]”，并且它将针对树的每个级别执行此操作。我希望我的逻辑清晰明了。但是，我得到的结果却是...

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

- buydadip

---

你的问题出在这一行代码：result[level].append(root.val)。例如，如果 result=[[]]*3，那么 result[0].append(1) 将会得到 [[1], [1], [1]]。节点出现的顺序可以通过跟踪递归轻松地进行调整。 - Unni

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]]

- Schidu Luca

Answer 2

我不懂Python，但你可能想看一下Python上的BFS实现。

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

供参考

# Python3 Program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict
 
# This class represents a directed graph
# using adjacency list representation
class Graph:
 
    # Constructor
    def __init__(self):
 
        # default dictionary to store graph
        self.graph = defaultdict(list)
 
    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)
 
    # Function to print a BFS of graph
    def BFS(self, s):
 
        # Mark all the vertices as not visited
        visited = [False] * (max(self.graph) + 1)
 
        # Create a queue for BFS
        queue = []
 
        # Mark the source node as
        # visited and enqueue it
        queue.append(s)
        visited[s] = True
 
        while queue:
 
            # Dequeue a vertex from
            # queue and print it
            s = queue.pop(0)
            print (s, end = " ")
 
            # Get all adjacent vertices of the
            # dequeued vertex s. If a adjacent
            # has not been visited, then mark it
            # visited and enqueue it
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True
 
# Driver code
 
# Create a graph given in
# the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
 
print ("Following is Breadth First Traversal"
                  " (starting from vertex 2)")
g.BFS(2)
 
# This code is contributed by Neelam Yadav

- Can Bayar

Answer 3

对于 @Schidu Luca 的答案进行了一些改进和变化

问题在于它的实现方式，子节点丢失了其父节点信息，尽管我们可以检索到它在树的哪个级别上。

添加映射关系：子节点 -> 父节点

nodes = []

def traverse(root, level, parent):
    if not root:
        return
    if level >= len(nodes):
        nodes_level = []
        nodes.append(nodes_level)
    parent_key = parent and parent.value or None
    nodes[level].append({root.value: parent_key})
    traverse(root.left, level + 1, root)
    traverse(root.right, level + 1, root)


traverse(self.root, 0, None)
return nodes

映射层级 -> 父级 -> 子级

nodes = {}
def traverse_mapped(root, level, parent):
    if not root:
        return
    if level >= len(nodes):
        nodes_level = {}
        nodes[level] = nodes_level
    parent_key = parent and parent.value or None
    if parent_key in nodes[level]:
        nodes[level][parent_key].append(root.value)
    else:
        nodes[level][parent_key] = [root.value]
    traverse_mapped(root.left, level + 1, root)
    traverse_mapped(root.right, level + 1, root)

traverse_mapped(self.root, 0, None)
return nodes

- Federico Baù