继续刷题，刷题果然会上瘾。

Python实现二叉树按层级遍历，看起来有点复杂。如下图，如果一个二叉树有多层，则从上到下，每层按从左到右遍历。

每层放在一个队列，整体返回一个多组队列的队列。

看起来复杂，其实实现反而很简单；不用栈，就用一个节点队列放当前层级节点，遍历当前层级节点，读取值放入一个读取队列，读取当前节点的子节点放入另一个队列；当当前队列节点遍历完成后，使用下一层节点对用，相当于进入下一层，遍历刚刚生成子节点队列，如此反复直到节点队列为空结束。

代码如下

# 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]]:
        traversalList = []
        nodeList = []
        if root != None:
            nodeList.append(root)
            while nodeList != []:
                currentLevelVal = []
                currentNodeList = []
                for node in nodeList:
                    currentLevelVal.append(node.val)
                    if node.left != None:
                        currentNodeList.append(node.left)
                    if node.right != None:
                        currentNodeList.append(node.right)
                traversalList.append(currentLevelVal)
                nodeList = currentNodeList
        return traversalList

ITPub博客

刷题系列 - Python实现二叉树按层级遍历

最新文章