简述实现二叉树层序遍历至二维数组 ?
参考答案:
二叉树的层序遍历是指按照树的层次,从上到下、从左到右遍历二叉树的节点。为了实现这个目标,我们可以使用队列(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
中,并继续下一轮循环,直到队列为空。这时,我们就得到了二叉树的层序遍历结果,即一个二维数组,其中每个子列表代表一层节点的值。