Я пытаюсь пройти зигзаг бинарного дерева. это не печать 5 последней ветки, почему?

Question

В коде нет проблемы с отступом

    class Node:
      def __init__(self,key):
        self.data=key
        self.left=None
        self.right=None
   def zig_zag(root):
    if not root:
        return
    s=[]
    l=1
    s.append(root)

    while s:
        q=[]
        if l%2==1:
            for i in reversed(s):
                print(i.data,end=' ')
                if i.left:q.append(i.left)
                if i.right:q.append(i.right)

        else:
            for i in s:
                print(i.data,end=' ')
                if i.left:q.append(i.left)
                if i.right:q.append(i.right)
        print(q)    
        s=q
        l+=1
root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(7)
root.left.right=Node(6)
root.right.left=Node(5)
root.right.left=Node(4)
zig_zag(root)

Вывод, который я получаю, равен [1,2,3,4,6,7] вместо [1,2,3,4,5,6,7]. Кто-нибудь может объяснить, почему он не добавляет 5 из последней ветки дерева

Answer 1

Сам алгоритм в порядке.
Но вы допустили ошибку в своем "коде добавления узла"
Вы устанавливаете root.right.left дважды

+ Изменить

root.right.left=Node(5)
root.right.left=Node(4)

в

root.right.left=Node(5)
root.right.right=Node(4)