题解 | #求二叉树的层序遍历#

NC15 求二叉树的层序遍历

描述:给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

例如：给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是 [ [3], [9,20], [15,7] ]

提示: 0 <= 二叉树的结点数 <= 1500

思路：深度优先遍历二叉树（虽然大学学过，但是我只记得名字，怎么遍历完全忘记了，不过不重要）。题目给的例子就是每一层的数据在一个数组里面。如果最终要返回的数据用result保存，则根节点（第0层）在结果result[0]中，值为[3]。根节点的子（第1层）为result[1]=[9,20]。根节点的孙（第2层）为result[2]=[15,7]。所以每层的结果都在result[level]中。所以我们只需要将每一层的val加入到result[level]中即可，即result[level].append(level层节点.val)，然后递归下去就行了。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    result = []
    def levelResult(self,root,level):
        if root == None:
            return None
        if len(self.result) <= level:
            self.result.append([])
        self.result[level].append(root.val)
        self.levelResult(root.left, level + 1)
        self.levelResult(root.right, level + 1)
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        self.levelResult(root,0)
        return self.result