обнаружение ошибки распечатки дерева порядка уровня - PullRequest
Новая
       27

обнаружение ошибки распечатки дерева порядка уровня

0 голосов
/ 10 марта 2019

Я реализовал обход дерева порядка уровней, однако он не распечатывает последние два узла. Я уверен, что это правильный подход, и я хочу, чтобы этот подход работал! Может кто-нибудь сказать мне, что я делаю неправильно в моем коде? 

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

import queue

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:        
        q = queue.Queue()
        q.put(root)
        self.level(root, q)

    def level(self, node, q):
        if node == None:
            return
        q.put(node.left)
        q.put(node.right)

        q = self.printyo(q)

        self.level(node.left, q)
        self.level(node.right, q)

    def printyo(self, q):
        if q.empty():
            return
        else:
            node = q.get()
            if node != None:
                print(node.val)
            return q

Тем не менее, 

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

Above code only prints out 

3
9
20

1 Ответ

1 голос
/ 10 марта 2019

Вы можете распечатать оставшиеся узлы с дополнительным отпечатком (вы добавили два узла для каждого вызова функции, поэтому вы должны также напечатать два в какой-то момент; неважно, когда вы работаете с очередью): 

def level(self, node, q):
    # ... code unchanged

    self.printyo(q)
    self.printyo(q)

    # ... code unchanged

Сказав это, я бы порекомендовал настроить вашу логику, чтобы узлы печатались в порядке уровней. Работайте итеративно или используйте некоторую конструкцию в своей рекурсии, чтобы убедиться, что ваша очередь заполнена в ширину, а не в глубину, которую вы используете здесь.

...