题解 | #求二叉树的层序遍历#

用BFS的思路去做遍历

1. 遍历第0层的所有结点，存入list里面；
2. 遍历第0层得到的list的所有结点，将这些结点的子节点存入下一层的list中；
3. 依次类推，拿出第i层的所有结点，将这些结点的子节点存入第i+1层的list，只要注意是从左往右放进list，遍历时从左向右遍历就行了。
4. 最后将二维的node list遍历一遍，变成value list就可以了。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root: TreeNode) :
        node_layer = [[root]] # 将各层的结点存起来
        i=1 # 从第1层开始
        while True:
            tmp_i = []
            for tmp_node in node_layer[i-1]:
                if tmp_node.left:
                    tmp_i.append(tmp_node.left)
                if tmp_node.right:
                    tmp_i.append(tmp_node.right)
            if len(tmp_i) == 0:
                break
            node_layer.append(tmp_i)
            i+=1
        # 将node list的val取出来
        for i in range(len(node_layer)):
            for j in range(len(node_layer[i])):
                node_layer[i][j] = node_layer[i][j].val
        return node_layer

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left  = TreeNode(15)
root.right.right = TreeNode(7)
print(Solution().levelOrder(root))