1. 链表

  1. struct ListNode
  2. {
  3.     int val;
  4.     ListNode *next;
  5.     ListNode() : val(0), next(nullptr) {}
  6.     ListNode(int x) : val(x), next(nullptr) {}
  7.     ListNode(int x, ListNode *next) : val(x), next(next) {}
  8. }

2. 二叉树

  1. 前序遍历

    1. class Solution {
    2. public:
    3.  vector<int> preorderTraversal(TreeNode* root) {
    4.      stack<TreeNode*> st;
    5.      vector<int> result;
    6.      st.push(root);
    7.      while (!st.empty()) {
    8.          TreeNode* node = st.top();                      // 中
    9.          st.pop();
    10.          if (node != NULL) result.push_back(node->val);
    11.          else continue;
    12.          st.push(node->right);                           // 右
    13.          st.push(node->left);                            // 左
    14.      }
    15.      return result;
    16.  }
    17. };

  2. 中序遍历

    1. class Solution {
    2. public:
    3.  vector<int> inorderTraversal(TreeNode* root) {
    4.      vector<int> result;
    5.      stack<TreeNode*> st;
    6.      TreeNode* cur = root;
    7.      while (cur != NULL || !st.empty()) {
    8.          if (cur != NULL) { // 指针来访问节点，访问到最底层
    9.              st.push(cur); // 讲访问的节点放进栈
    10.              cur = cur->left;                // 左
    11.          } else {
    12.              cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
    13.              st.pop();
    14.              result.push_back(cur->val);     // 中
    15.              cur = cur->right;               // 右
    16.          }
    17.      }
    18.      return result;
    19.  }
    20. };

  3. 后序遍历

    1. class Solution {
    2. public:
    4.  vector<int> postorderTraversal(TreeNode* root) {
    5.      stack<TreeNode*> st;
    6.      vector<int> result;
    7.      st.push(root);
    8.      while (!st.empty()) {
    9.          TreeNode* node = st.top();
    10.          st.pop();
    11.          if (node != NULL) result.push_back(node->val);
    12.          else continue;
    13.          st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序
    14.          st.push(node->right);
    15.      }
    16.      reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
    17.      return result;
    18.  }
    19. };


  5. 翻转二叉树

    3. xxxx

4. xxxx

References

二叉树非递归遍历 二叉树非递归遍历2[

](https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484687&idx=1&sn=85cd297b3c9927467e4048b1f50aa938&scene=21#wechat_redirect)