二叉树级顺序遍历-反向

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创建最多两个元素的子列表。这是不对的，因为显然，更宽的树将在同一层上具有更多的元素。您的算法没有规定将“表兄弟”放在同一列表中，只允许直接同级。

您的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