Binary Tree Inorder Traversal

这个问题用递归非常好解决, 但是作者要求使用迭代

这是一个以迭代实现子树遍历的做法, 值得做一下笔记

 

my solution

一开始我没看到 follow up, 然后用递归解决了

之后看到的时候没什么好的思路

(有部分是受了答案的影响, 因为这时候我已经解决了, 可以看别人的答案了)

(不得不说答案真是害人啊... 如果我独立思考的话, 花一部分时间也能想通的)

后面借鉴了答案的思想, 自己实现了, 所以这里就不贴出来了

 

best solution (4ms)

简单来说

  1. 遍历所有左子树
  2. 获得栈顶, 存值, 然后以其右子树继续遍历

重复以上步骤, 很简单吧 (但是我当时为什么没有想出来呢 ? ...)

以同样的逻辑, 可以实现 leftorder, rightorder

(如果没记错的话, 应该是这么叫的, 而且如果没估计错的话, 应该可以)