Python06 一个队列完成二叉树遍历

1 二叉树的概念

     A  
   /   \
  B     C
 / \   / \
D   E F   G

We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.

Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings.

（Quote from:https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html）

我们将链接数据结构的概念扩展到包含具有多个自引用字段的节点的结构。二叉树由节点组成，其中每个节点包含“左”引用，“右”引用和数据元素。树中最顶层的节点称为根。

树中的每个节点（不包括根）都通过来自其他节点的有向边连接。此节点称为父节点。另一方面，每个节点可以连接到任意数量的节点，称为子节点。没有子节点的节点称为叶子或外部节点。不是叶子的节点称为内部节点。具有相同父节点的节点称为兄弟节点。

2 队列的概念

1. Queues are open from both ends meaning elements are added from the back and removed from the front
2. The element to be added first is removed first (First In First Out - FIFO)
3. If all the elements are removed, then the queue is empty and if you try to remove elements from an empty queue, a warning or an error message is thrown.
4. If the queue is full and you add more elements to the queue, a warning or error message must be thrown.

Quote From https://www.pythoncentral.io/use-queue-beginners-guide/

1. 队列中进入点和出入点不同
2. Enqueue-向队列中添加元素
3. Dequeue-从队列中删除元素
4. 不允许随机访问-即无法从中间添加或者删除元素

import queue 
  
# From class queue, Queue is 
# created as an object Now L 
# is Queue of a maximum  
# capacity of 20 
L = queue.Queue(maxsize=20) 
  
# Data is inserted into Queue 
# using put() Data is inserted 
# at the end 
L.put(5) 
L.put(9) 
L.put(1) 
L.put(7) 
  
# get() takes data out from 
# the Queue from the head  
# of the Queue 
print(L.get()) 
print(L.get()) 
print(L.get()) 
print(L.get()) 

3 一个队列完成二叉树遍历

from collections import deque
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param root: A Tree
    @return: Level order a list of lists of integer
    """
    def levelOrder(self, root):
        if root is None:
            return []
            
        queue = deque([root])
        result = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        return result