跳到主要内容

简述实现二叉树层序遍历至二维数组 ?

参考答案:

二叉树的层序遍历是指按照树的层次,从上到下、从左到右遍历二叉树的节点。为了实现这个目标,我们可以使用队列(Queue)这种数据结构。队列的特性是先进先出(FIFO),这非常适合用来进行层序遍历。

下面是一个简单的 Python 代码示例,将二叉树的层序遍历结果存入一个二维数组:

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def levelOrder(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

在上述代码中,我们首先检查根节点是否存在。如果不存在,我们就返回一个空列表。然后,我们创建一个队列,并将根节点添加到队列中。

接下来,我们进入一个 while 循环,只要队列不为空,就继续循环。在每一次循环中,我们创建一个新的空列表 level,用于存储当前层的节点值。然后,我们遍历当前层的所有节点(即队列中的所有节点),并将它们的值添加到 level 列表中。同时,我们还将这些节点的左子节点和右子节点(如果存在的话)添加到队列中,以便在下一轮循环中处理。

最后,我们将 level 列表添加到结果列表 result 中,并继续下一轮循环,直到队列为空。这时,我们就得到了二叉树的层序遍历结果,即一个二维数组,其中每个子列表代表一层节点的值。