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

 

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import *


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q, cur_level, cur_list, rtn = [(root, 0)], 0, [], []
        while len(q) > 0:
            cur_node, level = q.pop()
            if level == cur_level:
                cur_list.append(cur_node.val)
            else:
                rtn.append(cur_list)
                cur_list = [cur_node.val]
                cur_level = level

            if cur_node.left:
                q.insert(0, (cur_node.left, level + 1))
            if cur_node.right:
                q.insert(0, (cur_node.right, level + 1))
        rtn.append(cur_list)
        return rtn


if __name__=='__main__':
    r = TreeNode(3)
    r.left = TreeNode(9)
    r.right = TreeNode(20)
    r.right.left = TreeNode(15)
    r.right.right = TreeNode(7)
    s = Solution()
    print(s.levelOrder(r))
