题目描述

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如: 给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

我的解法——记录本层+下层节点数（AC）

前序遍历(BFS)，使用一个Queue存储每层元素。
注意开始的root == null 的判断。
本题难点：需要分出每一层的结点数据来，所以需要判断当前结点是在哪一层。
时间时间复杂度均为O(n)，空间复杂度为O(n)。
Beat46%

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        que = []
        res = [[],]
        if(root == None or root.val == None):
            return []
        que.append(root)
        now = 0
        count_none_this = 0
        count_none_next = 0
        
        while(len(que) > 0):
            # 入队
            if(que[0].left != None and que[0].left.val != None):
                que.append(que[0].left)
            else:
                count_none_next += 1
            if(que[0].right != None and que[0].right.val != None):
                que.append(que[0].right)
            else:
                count_none_next += 1
            
            # 出队
            res[now].append(que[0].val)
            que = que[1:]
            
            # 判断循环终止
            if(len(res[now]) + count_none_this == pow(2,now)):
                if(len(res[now]) == 0):
                    break
                else:
                    count_none_this = count_none_next
                    count_none_next = count_none_next * 2  # 注意这里，下一层多一倍
                    
                # 加一层        
                res.append([])
                now += 1
            
        return res[:-1]

参考答案

https://www.cnblogs.com/love-yh/p/6961774.html