Двоичный уровень дерева Порядок обхода - обратный - PullRequest
Новая
       13

Двоичный уровень дерева Порядок обхода - обратный

2 голосов
/ 18 января 2020

Я пытаюсь решить эту проблему с кодом leetcode и не могу отладить ошибку !!

Прошло 3 часа, и я снова попытался переписать логи c, но я Я все еще что-то упускаю. Что еще я могу добавить, чтобы заставить его работать против контрольного примера: 

>>>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]

1 Ответ

1 голос
/ 18 января 2020

Ваш код может создавать только подсписки, содержащие до двух элементов, с помощью функции traverse_value. Это не может быть правильным, поскольку очевидно, что более широкие деревья будут иметь больше элементов на одном уровне. В вашем алгоритме нет положений о том, чтобы помещать «двоюродных братьев» в один и тот же список, только прямых братьев и сестер.

Ваш подход BFS, безусловно, является хорошей идеей, но убедитесь, что guish правильно различает слои, поэтому Вы знаете, когда помещать значения в тот же список или в новый один: 

    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
...