Skip to content

102. Binary Tree Level Order Traversal

难度: 中等

刷题内容

原题连接

  • https://leetcode.com/problems/binary-tree-level-order-traversal

内容描述

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

解题方案

思路 1

递归

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        self.recurHelper(root, 0, res)
        return res

    def recurHelper(self, root, level, res):
        if not root: return
        if len(res) < level + 1:
            res.append([])
        res[level].append(root.val)
        self.recurHelper(root.left, level+1, res)
        self.recurHelper(root.right, level+1, res)

思路 2

迭代,利用curLevel和nextLevel来记录,然后按层append.

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res, cur_level = [], [root]
        while cur_level:
            next_level, tmp_res = [], []
            for node in cur_level:
                tmp_res.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            res.append(tmp_res)
            cur_level = next_level
        return res


回到顶部