0107._binary_tree_level_oprder_traversal_ii.md

Navigation

• Navigation
• Links:
• Tags
• Solution 1 DFS，递归
• Solution 2 DFS，迭代，利用Stack
• Solution 3 BFS，利用队列
• Solution 4 BFS变种
• 总结

Links:

1. https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
2. https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

Tags

1. 树
2. 广度优先

Solution 1 DFS，递归

class Solution(object):
    def levelOrderBottom(self, root):
        res = []
        self.dfs(root, 0, res)
        return res[::-1]

    def dfs(self, root, level, res):
        if root:    # 证明当前层有元素
            if len(res) == level:   # 添加容器
                res.append([])
            res[level].append(root.val)
            self.dfs(root.left, level+1, res)
            self.dfs(root.right, level+1, res)

Solution 2 DFS，迭代，利用Stack

class Solution(object):
    def levelOrderBottom(self, root):
        stack = [(root, 0)]
        res = []

        while stack:
            node, level = stack.pop()
            if node:
                if len(res) == level:
                    res.append([])
                res[level].append(node.val)
                stack.append((node.right, level+1)) # 因为是栈，所以left和right顺序要掉转。在栈中，使得当前层的left在right上面。
                stack.append((node.left, level+1))

        return res[::-1]

Solution 3 BFS，利用队列

class Solution(object):
    def levelOrderBottom(self, root):
        queue = collections.deque([(root, 0)])
        res = []

        while queue:
            node, level = queue.popleft()

            if node:
                if len(res) == level:
                    res.append([])
                res[level].append(node.val)
                queue.append((node.left, level+1))
                queue.append((node.right, level+1))

        return res[::-1]

Solution 4 BFS变种

class Solution(object):
    def levelOrderBottom(self, root):
        if not root:
            return
        
        result = []
        row = [root]
        
        while row:
            result = [[r.val for r in row]] + result
            row = [child_node for parent_node in row for child_node in [parent_node.left, parent_node.right] if child_node]
        return result

总结

Solution 1和2都是在DFS过程中构建答案。 Solution 4每次while循环直接构造一层。而Solution 3每次while循环每次构造一个节点。 实质上都是考二叉树的遍历。