给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。
例如: 给定二叉树: [3,9,20,null,null,15,7],
3
/ <br> 9 20
/ <br> 15 7
返回其层次遍历结果:
[ [3], [9,20], [15,7] ]
思路:首先观察返回值格式为一个二维数组,第 i 行表示二叉树的第 i 层,可以使用队列来协助进行层序遍历,队列每一次也传入一个一维数组[ node, level],其中node表示二叉树的节点,level表示该节点所处的层数,每遍历至一个节点就将该节点的左右子节点信息存入队列中去,再从队列中取出一组信息,依次循环。
注意result的行数要随着level的增加而增加,每向下遍历一层,result行数+1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
import queue
result = [[]]
q = queue.Queue()
if root == None:
return []
q.put([root, 0]) # 第一个数据为节点,第二个数据为层数
while not q.empty():
temp = q.get()
node = temp[0] # 节点
level = temp[1] # 层数
if level == len(result):
result.append([])
result[level].append(node.val)
if node.left:
q.put([node.left, level + 1])
if node.right:
q.put([node.right, level + 1])
return result
本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://wangjiawei.blog.csdn.net/article/details/103508607