算法: 二叉树级顺序遍历 (3种解法)102. Binary Tree Level Order Traversal102. Binary Tree Level Order Traversal1. BFS广度优先解法一2. BFS 简化解法二3. BFS 简化解法三参考

159 阅读 0 评论 105 点赞

我是靠谱客的博主安详超短裙，这篇文章主要介绍算法: 二叉树级顺序遍历 (3种解法)102. Binary Tree Level Order Traversal102. Binary Tree Level Order Traversal1. BFS广度优先解法一2. BFS 简化解法二3. BFS 简化解法三参考，现在分享给大家，希望可以做个参考。

102. Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:
在这里插入图片描述

复制代码

1
2
3
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

复制代码

1
2
3
Input: root = [1]
Output: [[1]]

Example 3:

复制代码

1
2
3
Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

1. BFS广度优先解法一

level是当前关卡中的节点列表。继续将这些节点的值列表附加到下一个级别（孩子）中的所有节点ans，然后更新level，直到它达到一个空级别。Python 的列表推导使得以简洁的方式处理许多条件变得更加容易。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
def levelOrder(self, root):
    if not root:
        return []
    ans, level = [], [root]
    while level:
        ans.append([node.val for node in level])
        temp = []
        for node in level:
            temp.extend([node.left, node.right])
        level = [leaf for leaf in temp if leaf]
    return ans

2. BFS 简化解法二

复制代码

1
2
3
4
5
6
7
8
def levelOrder(self, root):
    ans, level = [], [root]
    while root and level:
        ans.append([node.val for node in level])
        LRpair = [(node.left, node.right) for node in level]
        level = [leaf for LR in LRpair for leaf in LR if leaf]
    return ans

3. BFS 简化解法三

复制代码

1
2
3
4
5
6
7
def levelOrder(self, root):
    ans, level = [], [root]
    while root and level:
        ans.append([node.val for node in level])            
        level = [kid for n in level for kid in (n.left, n.right) if kid]
    return ans