07 Jun 2017

LeetCode-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],

return its level order traversal as:

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

# _*_ coding: utf-8 _*_


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


class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        n_last = last = root
        _queue = [root]
        result, temp = [], []
        while _queue:
            node = _queue.pop(0)
            temp.append(node.val)
            if node.left:
                _queue.append(node.left)
                n_last = node.left
            if node.right:
                _queue.append(node.right)
                n_last = node.right
            if node == last:
                result.append(temp)
                last = n_last
                temp = []
        return result

    def levelOrder1(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res, level = [], [root]
        while root and level:
            # 先倒出所有不为空的叶子
            res.append([n.val for n in level if n])
            # 用之前的叶子找到下一层不为空的叶子
            level = [kid for n in level for kid in (n.left, n.right) if kid]
        return res

不会跑

LeetCode-binary-tree-level-order-traversal