【leetcode】102. Binary Tree Level Order Traversal解题报告

给定一棵二叉树，对其进行层次遍历，将其结果存按层存放到一个二维数组中。
思路1：
采用非递归方式，层次遍历的非递归方式一般要要用到队列，队列有一端进一端出的特点，将要访问的节点出队列，访问该节点后将其左右孩子节点放到队列的末尾即可实现层次遍历。
如何将节点的值按层保存呢，层次遍历时，首先看队列的长度，队列的当前长度就是当前层所包含的节点的个数，在一开始进行层次遍历时就记录当前队列的长度count，在该层出队列count个节点即可。
AC代码

    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root == None:
            return []
        res = []
        import collections
        queue = collections.deque()
        queue.append(root)

        while(len(queue)!=0):
            count = len(queue)
            tmp = []
            for i in range(count):
                top = queue.popleft()
                tmp.append(top.val)
                if top.left != None:
                    queue.append(top.left)
                if top.right != None:
                    queue.append(top.right)
            res.append(tmp)
        return res

思路2：
采用递归方式
递归函数中，需要一个记录当前层数的变量level_count，然后根据这个level_count找到数组对应的位置添加元素即可。

class Solution:
    def levelOrder(self, root):
        self.level_count = 0
        self.res = []
        self.BFS(root,0)
        return self.res

    def BFS(self,root,level_count):
        if root == None:
            return
        else:
            if len(self.res) < level_count+1:
                self.res.append([])
            self.res[level_count].append(root.val)
            self.BFS(root.left, level_count+1)
            self.BFS(root.right, level_count+1)