基础知识-层序遍历(python)

昨晚入睡前突然想到其实层序遍历和构建二叉树的过程非常类似，早上起来赶快把代码写出来验证一下。
二叉树的构建是通过一个数组来保存子树还未构建完成的节点（下面把这个数组称为myQueue），在每次添加元素的时候从myQueue取出myQueue[0]构建其左右子树，并且把左右孩子节点加入myQueue中等待构建他们的子树。当该节点的左右子树都构建完成的时候就把这个节点pop出去，这样myQueue中节点的顺序就是按一层层节点的顺序排列的来等待构建。

层序遍历和构建二叉树的过程基本相同，也是需要一个数组queue来保存还未访问的节点，因为构建二叉树的时候就是按照一层一层构建的，所以层序遍历其实只是把构建子树的操作换成访问节点的操作，
每次先pop出该节点，在每次访问的时候把该节点的左右节点的值打印出来并且把该节点的左右孩子append到queue中，这样的pop和访问的操作就能层序遍历出所有节点。

def levelOrder(tree):
    if tree.root is None:  # 如果是空树， 打印空数组， 结束程序
        print([])
        return
    queueOrder = [tree.root]  # queueOrder用来保存即将被遍历的节点

    while queueOrder:
        print(queueOrder[0].val)
        node = queueOrder.pop(0)
        if node.left:
            queueOrder.append(node.left)
        if node.right:
            queueOrder.append(node.right)