首页 > 其他 > 详细

Leetcode 102. Binary Tree Level Order Traversal

时间:2017-02-18 00:43:47      阅读:130      评论:0      收藏:0      [点我收藏+]

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

思路: 逐个level操作。用queue来维护每一行,对于每一行pop出第一个node的时候,把他的left和right kid push到queue里面。注意应该先算出这一行到底有多少个node (也就是当前queue的长度),否则不知道什么时候该停下来。

 1 # Definition for a binary tree node.
 2 # class TreeNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution(object):
 9     def levelOrder(self, root):
10         """
11         :type root: TreeNode
12         :rtype: List[List[int]]
13         """
14         if not root:
15             return []
16         
17         ans = []    
18         queue = [root]
19         while queue:
20             level = []
21             size = len(queue)
22             for i in range(size):
23                 node = queue.pop(0)
24                 level.append(node.val)
25                 if node.left:
26                     queue.append(node.left)
27                 if node.right:
28                     queue.append(node.right)
29             ans.append(level)
30         return ans

 

Leetcode 102. Binary Tree Level Order Traversal

原文:http://www.cnblogs.com/lettuan/p/6412075.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!