二叉树级顺序遍历 - 反向

Question

我正在 leetcode 上尝试这个编码问题，但无法调试错误！

已经 3 个小时了，我尝试再次重写逻辑，但我仍然遗漏了一些东西。我还可以添加什么以使其适用于测试用例：

>>>input - [1,2,3,4,null,null,5]

>>>expected output - [[4,5],[2,3],[1]]

尽管此代码适用于给定的测试用例：

>>> input - [3,9,20,null,null,15,7]

>>> output - [[15,7],[9,20],[3]]

这是我的努力：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:

        queue = []
        level = []

        result = []

        if root is None:
            return None

        result.append([root.val])
        queue.append(root)

        while len(queue) > 0:
            a = queue[0]

            ans = self.traverse_value(a.left, a.right, queue)

            if ans is not None:
                result.append(ans)

            queue.pop(0)

        return reversed(result)


    def traverse_value(self, r_left, r_right, queue):

        if r_left is None and r_right is None: # both l and r are none
            return
        elif r_left is None and r_right is not None: # right is not none
            queue.append(r_right)
            return [r_right.val]
        elif r_left is not None and r_right is None: # left is not none
            queue.append(r_left)
            return [r_left.val]
        elif r_left is not None and r_right is not None: # both are not none
            queue.append(r_left)
            queue.append(r_right)
            return [r_left.val, r_right.val]

Answer 1

您的代码只能通过函数 traverse_value 创建最多包含两个元素的子列表。这不可能是正确的，因为显然更宽的树将在同一层上有更多的元素。您的算法没有规定将 "cousins" 放在同一个列表中，只有直系兄弟姐妹。

您的 BFS 方法当然是个好主意，但请确保正确区分层，以便您知道何时将值放入 same 列表或 new一个：

    result = []
    if root is None:
        return None
    queue = [root]
    while len(queue):
        # get the values out of the current queue
        result.append([a.val for a in queue])
        # perform a separate loop for the this layer only
        nextlayer = []
        for a in queue:
            # just extend this new list for the whole layer
            if a.left:
                nextlayer.append(a.left)
            if a.right:
                nextlayer.append(a.right)
        # finally put that whole layer in the queue
        queue = nextlayer

    return reversed(result)

对于您的信息，它也可以通过 DFS 解决方案来完成，您只需跟踪您所在的深度，并将其用作解决方案列表中的索引：

    level = []
    def recur(node, depth):
        if not node:
            return
        if depth >= len(level):
            level.append([])
        level[depth].append(node.val)
        recur(node.left, depth+1)
        recur(node.right, depth+1)

    recur(root, 0)
    level.reverse()
    return level

二叉树级顺序遍历 - 反向

Binary Tree Level Order traversal - reversed

python

binary-tree

traversal