Iterative Traversal本质是把稍后要处理的Node放到stack上，然后依逻辑不断地pop和push，直到stack为空。每次iteration，都从stack上pop出一个node，然后根据其状态采取不同的处理。理论上，每次对node的访问，可以有三种状态：from parent node, from left child and from right child。再往深入想，状态的数量其实是由print的顺序决定的。Node之所以被放入stack，是因为要在将来某时刻print，换句话说，一旦该node完成了print，它就不会再次被访问。 Pre-Order Traversal 第一次访问node，就立刻print，此后不会有第二次访问该node的可能性。所以对于pre-order，pop出来的node只有一种状态，不需要额外的flag来指示状态。 In-Order Traversal Node在第二次访问时才会被打印，因此有两个状态：from parent node and from left child。所以，用一个boolean就可以区分两种状态。需要注意的是第二次访问时才从stack中pop，所以在进入循环时选择peek。 老师给的解法其实很有技巧性。helper为null时表示从from left child，反之则表示from parent… Read more “Thoughts on Binary Tree Iterative Traversal”