17
LeetCode: 102. Binary Tree Level Order Traversal
source link: https://mozillazg.com/2021/01/leetcode-102-binary-tree-level-order-traversal.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
题目¶
原题地址：https://leetcode.com/problems/binary-tree-level-order-traversal/
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
解法¶
广度优先，从上到下一层一层遍历，保存每一层的 value。
这个方法的 Python 代码类似下面这样:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
all_values = []
next_level_nodes = [root]
while next_level_nodes:
current_nodes = next_level_nodes
values = []
next_level_nodes = []
for node in current_nodes:
values.append(node.val)
if node.left is not None:
next_level_nodes.append(node.left)
if node.right is not None:
next_level_nodes.append(node.right)
if values:
all_values.append(values)
return all_values
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK