- Binary Tree Level Order Traversal
中等
https://leetcode-cn.com/problems/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:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000
相关企业
- 字节跳动|12
- Facebook|9
- 亚马逊 Amazon|9
- 微软 Microsoft|7
- 彭博 Bloomberg|5
相关标签
- Tree
- Breadth-First Search
- Binary Tree
相似题目
- Binary Tree Zigzag Level Order Traversal 中等
- Binary Tree Level Order Traversal II 中等
- Minimum Depth of Binary Tree 简单
- Binary Tree Vertical Order Traversal 中等
- Average of Levels in Binary Tree 简单
- N-ary Tree Level Order Traversal 中等
- Cousins in Binary Tree 简单
- BFS use 1 queue
- use 1 queue to record next-level nodes.
- Use length to control each level iteration.
- BFS use 2 queues
- use 2 queues to record current level and next level in turn.
- use
for node in myqueue_currleveldirectly to iterate
- BFS use dummy node
- use 1 queue. use dummy node (None here) to idicate the end of each level.
- DFS recursion
- use 1 queue to record next-level nodes.
- Use leng to control each level iteration.
# 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
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
# push first level nodes
myqueue = deque([root]) # left is head/first
result = []
while myqueue:
result_curr_level = []
# use each node in this level to extend all nodes in next level
for _ in range(len(myqueue)): # only len() operate once
currNode = myqueue.popleft()
# record each node in this level
result_curr_level.append(currNode.val)
# record nodes in next level
if currNode.left:
myqueue.append(currNode.left)
if currNode.right:
myqueue.append(currNode.right)
result.append(result_curr_level)
return resultfrom collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
myqueue = deque([root]) # left is head/first
result = [[root.val]] # first level
while len(myqueue) != 0:
result_curr_level = []
templeng = len(myqueue)
for _ in range(templeng): # extend to next level
currNode = myqueue.popleft()
if currNode.left:
myqueue.append(currNode.left)
result_curr_level.append(currNode.left.val) # add next-level nodes
if currNode.right:
myqueue.append(currNode.right)
result_curr_level.append(currNode.right.val)
if result_curr_level:
result.append(result_curr_level)
return result- use 2 queues to record current level and next level in turn.
- use
for node in myqueue_currleveldirectly to iterate
# 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 not root:
return []
myqueue_currlevel = deque([root])
result = []
while myqueue_currlevel:
# record this level
result.append([node.val for node in myqueue_currlevel])
# extend next level
myqueue_nextlevel = deque()
for node in myqueue_currlevel:
if node.left:
myqueue_nextlevel.append(node.left) # push
if node.right:
myqueue_nextlevel.append(node.right)
myqueue_currlevel = myqueue_nextlevel
return result- use 1 queue. use dummy node (None here) to idicate the end of each level.
# 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 not root:
return []
myqueue = deque([root, None])
result = []
result_currlevel = []
while myqueue:
currNode = myqueue.popleft()
# meet dummy node which means last of curr level
if currNode is None:
result.append(result_currlevel)
result_currlevel = []
if myqueue:
myqueue.append(None)
continue
# record curr-level node
result_currlevel.append(currNode.val)
# record next-level nodes
if currNode.left:
myqueue.append(currNode.left) # push
if currNode.right:
myqueue.append(currNode.right)
return resultuse dfs to go over all nodes. Add node to corresponding level-list. DFS只是用来遍历，加入每一层的时候用currRecordLevel变量来判断。
# 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 not root:
return []
results = [] # results[i] is level i
# use dfs to go over all nodes. Add node to corresponding level-list.
self.dfs(root, 1, results)
return results
def dfs(self, currnode, currRecordLevel, results):
if not currnode:
return
if len(results) < currRecordLevel:
for i in range(currRecordLevel - len(results)):
results.append([]) # avoid out-of-index-range error
results[currRecordLevel-1].append(currnode.val)
self.dfs(currnode.left, currRecordLevel+1, results)
self.dfs(currnode.right, currRecordLevel+1, results)