https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

没看题解写出来了，但是我写的是个BFS+双指针，一开始没想到要用队列做，感觉大概就是用双指针模拟了队列？

用left和right这两个指针是否相等来表明是否处理完了这一层

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        
        node_list =[root]
        flag = 0
        left = 0
        right = 0
        re = [[root.val]]
        temp_re = []
        while flag < len(node_list):
            node_list, _ = self.node_handler(node_list[flag], node_list)
            temp_re = temp_re + _
            flag += 1
            if left == right:
                if temp_re is None or len(temp_re) < 1:
                    pass
                else:
                    re.append(temp_re)
                left = flag
                right = left + len(temp_re) - 1
                temp_re = []
            else:
                left += 1
        return re

            

    def node_handler(self, node, node_list):
        if node.left != None and node.right != None:
            node_list.append(node.left)
            node_list.append(node.right)
            return node_list, [node.left.val, node.right.val]
        
        if node.left is None and node.right != None:
            node_list.append(node.right)
            return node_list, [node.right.val]
        
        if node.right is None and node.left != None:
            node_list.append(node.left)
            return node_list, [node.left.val]

        return node_list, []

时间复杂度O(n)，因为有一重循环。空间复杂度O(n)。


下面这个是BFS+queue的写法，显然这个写法很容易看懂，合理利用数据结构可以有效提高编码效率。思路就是队列里面只保存这一层的节点，这一层的节点算完就pop出去，和我上面那个想法差不多，只不过我是用了left和right这两个指针代替了队列。


实际上队列不就可以用列表/数组+一个指针来实现么

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        import queue
        q = queue.Queue()

        q.put(root)
        re = [[root.val]]
        while q.qsize() != 0:
            temp = []
            for i in range(q.qsize()):
                node = q.get()
                if node.left != None:
                    q.put(node.left)
                    temp.append(node.left.val)
                if node.right != None:
                    q.put(node.right)
                    temp.append(node.right.val)
            if len(temp) > 0:
                re.append(temp)
        
        return re