1.二叉树的非递归中序遍历算法
二叉树的中序遍历方法是：左中右，因此一开始会顺着根节点的左孩子一直往下（这点和先序遍历一样，这也是二者前面部分代码很相似的原因），到最后一个左孩子时尝试把它的右孩子塞进栈内，然后顺着它的的左孩子而下，直到不能访问为止。利用的栈FILO的特性，对每个节点都进行顺左孩子而下即可。
上代码：
1 void inOrder(TreeNode* root,vector<int>& inOrder) 2 { 3 stack<TreeNode*>st; 4 TreeNode* p = root; 5 while (p != nullptr || !st.empty()) 6 { 7 while (p != nullptr) 8 { 9 st.push(p); 10 p = p->left; 11 } 12 if (!st.empty()) 13 { 14 auto top = st.top(); 15 inOrder.push_back(top->val); 16 st.pop(); 17 p = top->left; 18 } 19 } 20 }
具体实现可以参考这篇文章：https://www.jianshu.com/p/49c8cfd07410，当然我的思(dai)路(ma)也是从这里获(chao)取(xi)的(??保命)
原文：https://www.cnblogs.com/Swetchine/p/11260926.html