【数据结构与算法】【LeetCode】【二叉树】107.二叉树的层序遍历II

# Definition for a binary tree node.
from queue import Queue

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def create_tree(list_tree):
    if  not list_tree:
        return []
    new_queue= Queue()
    root = TreeNode(list_tree[0])
    new_queue.put(root) # 先入队一个结点
    count = 1
    while not new_queue.empty() and count<len(list_tree):
        dequeue = new_queue.get() # 出队
        if not dequeue.left and  not dequeue.right:
            if count<len(list_tree) and list_tree[count]:
                dequeue.left=TreeNode(list_tree[count])
            count= count+1
            if count<len(list_tree) and list_tree[count]:
                dequeue.right=TreeNode(list_tree[count])
            count= count+1

            if dequeue.left:
                new_queue.put(dequeue.left)
            if dequeue.right:
                new_queue.put(dequeue.right)
    return root
class Solution:
    def levelOrder(self, root: TreeNode):
        if not root:
            return []
        
        new_queue=Queue()
        list_level=[]
        # 初始化队列
        new_queue.put(root)
        while not new_queue.empty():  
            count =new_queue.qsize() # 统计每层结点个数
            tmp=[]
            while count: # 使每层结点都出队，并让下一层结点入队
                dequeue= new_queue.get()
                tmp.append(dequeue.val)
                if dequeue.left:
                    new_queue.put(dequeue.left)
                if dequeue.right:
                    new_queue.put(dequeue.right)
                count= count-1
            list_level.append(tmp)
        return list_level[::-1]
                   

root = [3,9,20,None,None,15,7]
root_tree=create_tree(root)
a=Solution()
result =a.levelOrder(root_tree)
result

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        def dfs(index,r):
            # 假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
            if len(res)<index:
                res.append([])
            #  将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
            # res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
            res[index-1].append(r.val)
            # 递归的处理左子树，右子树，同时将层数index+1
            if r.left:
                dfs(index+1,r.left)
            if r.right:
                dfs(index+1,r.right)
        dfs(1,root)
        return res[::-1]
root = [3,9,20,None,None,15,7]
root_tree=create_tree(root)
a=Solution()
result =a.levelOrder(root_tree)
result