Given a binary tree, design an algorithm that does a level order traversal of the tree, where each level is printed out in the reverse order as the previous level.

Question

Sigiloso · Accepted Answer

from Queue import Queue
from collections import defaultdict
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.right = None
        self.left = None
def levelOrder(root):
    levelorderdict = defaultdict(list)
    q = Queue()
    q.put((root, 0, True))
    levelorderdict[0].append(root.val)
    while not q.empty():
        node, level, reverse = q.get()
        if node.left is not None:
            if reverse:
                levelorderdict[level + 1] = [node.left.val] + levelorderdict[level + 1]
            else:
                levelorderdict[level + 1] += [node.left.val]
            q.put((node.left, level + 1, not reverse))
        if node.right is not None:
            if reverse:
                levelorderdict[level + 1] = [node.right.val] + levelorderdict[level + 1]
            else:
                levelorderdict[level + 1] += [node.right.val]
            q.put((node.right, level + 1, not reverse))
    for level, List in dict(levelorderdict).items():
        print List

# Test Case
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(3)
root.left.left = TreeNode(1)
root.left.right = TreeNode(10)
root.right.left = TreeNode(6)

levelOrder(root)

RetailMeNot

Pergunta de entrevista da empresa RetailMeNot

Resposta da entrevista

Empresas seguidas

Buscas de vagas