# coding=utf-8

"""
二叉树的层次遍历 II

给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）

思路:其实就是把二叉树的层次遍历的结果倒序输出
"""

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: A tree
    @return: buttom-up level order a list of lists of integer
    """
    def levelOrderBottom(self, root):
        # write your code here
        if not root:
            return []
        result = []
        queue = [root]
        while queue:
            next_queue = []
            result.append([node.val for node in queue])
            for node in queue:
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            queue = next_queue
        return result[::-1]
# coding=utf-8

"""
二叉树的层次遍历 II

给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）

思路:其实就是把二叉树的层次遍历的结果倒序输出
"""

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: A tree
    @return: buttom-up level order a list of lists of integer
    """
    def levelOrderBottom(self, root):
        # write your code here
        if not root:
            return []
        result = []
        queue = [root]
        while queue:
            next_queue = []
            result.append([node.val for node in queue])
            for node in queue:
                if node.left:
                    next_queue.append(node.left)
                if node.right:
                    next_queue.append(node.right)
            queue = next_queue
        return result[::-1]
# coding=utf-8 二叉树的层次遍历 II  给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）  思路:其实就是把二叉树的层次遍历的结果倒序输出 Definition of TreeNode: class TreeNode:     def __init__(self, val):         self.val = val         self.left, self.right = None, None @param root: A tree     @return: buttom-up level order a list of lists of integer # write your code here