目录

1、二叉树层次遍历

2、二叉树层次遍历进阶

1、二叉树层次遍历

思想：首先将根节点入队列，在每次循环中，记录当前层的节点个数，然后依次弹出队列中的节点，并将其值添加到当前层的列表。如果节点存在左孩子，将左孩子入队列；如果节点存在右孩子，将右孩子入队列。最后，将当前层的结果添加到结果列表中，并重复此过程直到队列为空

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef levelOrder(root):# 如果根节点为空，则返回空列表if not root:return []result = []# 使用队列来进行层次遍历，将根节点入队列queue = [root]while queue:# level_size：当前层的节点个数level_size = len(queue)# current_level：存储当前层节点值的列表current_level = []# 遍历当前层的节点for i in range(level_size):# 弹出队列中的第一个节点，并且将将节点值添加到当前层列表current_level中node = queue.pop(0)current_level.append(node.val)# 层次遍历是从左到右的，先判断是否有左孩子if node.left:queue.append(node.left)if node.right:queue.append(node.right)# 遍历完一层加到结果中result.append(current_level)return result# 创建一个二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)
# 进行层次遍历
result = levelOrder(root)
print(result)  # 输出 [[1], [2, 3], [4, 5]]

2、二叉树层次遍历进阶

修改：假设第一层是第0层，奇数层从左向右，偶数层从右向左遍历

思想：在遍历过程中使用 is_odd_level 变量来表示当前层是否为奇数层，根据不同的情况选择并将其值添加到当前层的列表中，遍历完一层之后，翻转 is_odd_level 的值来切换到下一层

# 奇数从左向右，偶数从右向左class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef levelOrder(root):# 如果根节点为空，则返回空列表if not root:return []result = []# 使用队列来进行层次遍历，将根节点入队列queue = [root]# 标识位，判断当前层是否是奇数层is_odd_level = Falsewhile queue:# level_size：当前层的节点个数level_size = len(queue)# current_level：存储当前层节点值的列表current_level = []# 遍历当前层的节点for i in range(level_size):node = queue.pop(0)# 奇数层从左向右if is_odd_level:current_level.append(node.val)# 偶数层从右向左else:current_level.insert(0, node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)# 遍历完一层加到结果中result.append(current_level)# 切换到下一层时，反转is_odd_level = not is_odd_levelreturn result# 创建一个二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# 进行层次遍历
result = levelOrder(root)
print(result)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！