[leetcode]Binary Tree Level Order Traversal II @ Python

原题地址:http://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

题意:

Given a binary tree, return the bottom-up level order traversal of its nodes‘ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   /   9  20
    /     15   7

 

return its bottom-up level order traversal as:

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

 

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


OJ‘s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.

Here‘s an example:

   1
  /  2   3
    /
   4
         5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
解题思路:由于编程语言为python,所以其实在Binary Tree Level Order Traversal这道题(http://www.cnblogs.com/zuoyuan/p/3722004.html)的基础上加一句res.reverse()就可以了。
代码:
# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of lists of integers
    def preorder(self, root, level, res):
        if root:
            if len(res) < level+1: res.append([])
            res[level].append(root.val)
            self.preorder(root.left, level+1, res)
            self.preorder(root.right, level+1, res)
            
    def levelOrderBottom(self, root):
        res=[]
        self.preorder(root, 0, res)
        res.reverse()
        return res

 

[leetcode]Binary Tree Level Order Traversal II @ Python,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。