How to iterate through a tree in spiral order?

           1 
      2              3
  4       5        6       7
8  9   10   11   12 13   14  15   
开发者_Go百科

the output in spiral order should be 1 3 2 4 5 6 7 15 14 13 12 11 10 9 8

Think about how you would iterate through the root node and the first level.

Can you write a function for that behavior, and call it recursively?

This is really a variation of a breadth-first search. A breadth-first search uses a queue to get a list of the nodes at the next level down. A queue is a FIFO (first in first out). If you reverse the order at each level you'll get this effect so you need a LIFO (last in first out) instead, otherwise known as a stack.