原題鏈接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]
]
常規(guī)層序遍歷江锨，用一個隊(duì)列保存同級的結(jié)點(diǎn)熊楼，在遍歷時(shí)將下一層結(jié)點(diǎn)入隊(duì)蝴蜓，同時(shí)用count統(tǒng)計(jì)下一層結(jié)點(diǎn)數(shù)量闽坡，當(dāng)本層遍歷數(shù)量自增到上次保留的count值后槐壳，本層遍歷結(jié)束莺葫，進(jìn)入下一層結(jié)點(diǎn)垒棋，同時(shí)更新count值褐捻，得到的本層res爬范，進(jìn)入res_stack父腕。直到隊(duì)列為空，輸出res_stack青瀑。
# 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 []
deques = deque()
res_stack = []
deques.append(root)
count = 1
while deques:
res = []
n = count
count = 0
i = 0
while i < n:
item = deques.popleft()
res.append(item.val)
i += 1
if item.left:
count += 1
deques.append(item.left)
if item.right:
count += 1
deques.append(item.right)
res_stack.append(res)
return res_stack
