首页 > itarticle > leetcode_binary tree level order traversal ii

leetcode_binary tree level order traversal ii

admin 11月 13, 2020 0

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).
（从底向上按层遍历二叉树）

Example:

1. 递归

按层遍历，每次都把同层的树节点 Node 组合成一个 List 输入到队列。（变形之后的BFS）。(只需要把Binary Tree Level Order Traversal结果倒叙存储即可) 具体实现过程如下：


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

class :
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        results = [[root.val]]
        
        queue = []
        queue.append([root])
        while len(queue):
            top = queue.pop()
            
            result = []
            level_node = []
            for node in top:
                if node.left:
                    level_node.append(node.left)
                    result.append(node.left.val)
                if node.right:
                    level_node.append(node.right)
                    result.append(node.right.val)
            if result:
                queue.insert(0, level_node)
                results.insert(0, result)
           
        return results