Category Archives: Computer Theory

Tips for traversing a tree with stacks


Here are the tips of my solution:

  • You always push the root to the stack first
  • The most difficult part is: when you see a node on the top of element, should you go on to push its children, or pop it to print it? 
    • For pre-order traversal, you can pop it then push their children.  
    • For in-order traversal, you need to check whether its left child has been popped yet.  If yes, pop it; else, push its left child. 
      • You can add a flag to the node when it is pushed to stack with initial value equals to False.  
      • Enquiry this flag before deciding whether to pop current node.  If True, do a pop; If False, set this flag as True before pushing its left child. 
      • You should set the flag to True even if its left child is Null
    • For post-order traversal, you need to check whether both its children have been popped yet. This time you need two flags. 


阻塞且同步: read()方法要等到读到数据了才返回,如果没数据就会一直等

非阻塞且同步: read()方法如果发现当前没数据,就会返回; 调用者可以去做别的事情。然后过段时间再读(轮询)

非阻塞且异步:read()方法如果发现当前没数据,会返回; 调用者可以去做别的事情,也不用再轮询,等操作系统把数据读好了,会通过回调方式把数据交给调用者。

阻塞并异步: 没有这样的组合,这种组合也没有意义



  同步/异步:   读不到数据需要主动重试,就是同步; 如果数据好了惊醒你,就是异步。