problem address
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] ]注意要找到当前层的所有节点继续向下遍历
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def levelOrder(self, root: TreeNode) -> List[List[int]]: if not root: # NOTE: 注意root可能为空 return [] res = [] cur_nodes = [root] next_nodes = [] res.append([i.val for i in cur_nodes]) while cur_nodes or next_nodes: for node in cur_nodes: if node.left: next_nodes.append(node.left) if node.right: next_nodes.append(node.right) if next_nodes: res.append( [i.val for i in next_nodes] ) cur_nodes = next_nodes next_nodes = [] return res