【C++】二叉树的前序、中序、后序遍历(递归、非递归)

#include <vector>
#include <iostream>
#include <string>
using namespace std;
//二叉树的定义
struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int a) :val(a), left(NULL), right(NULL) {}
};
//使用递归进行前序遍历
void preoder(TreeNode* cur, std::vector<int>& ret) {
  ret.push_back(cur->val);
  preoder(cur->left, ret);
  preoder(cur->right, ret);
}
//使用递归进行中序遍历
void inoder(TreeNode* cur, std::vector<int>& ret) {
  inoder(cur->left, ret);
  ret.push_back(cur->val);
  inoder(cur->right, ret);
}
//使用递归进行后序遍历
void backoder(TreeNode* cur, std::vector<int>& ret) {
  preoder(cur->left, ret);
  preoder(cur->right, ret);
  ret.push_back(cur->val);
}
//使用栈进行前序遍历
vector<int> preoder1(TreeNode* root) {
  stack<TreeNode*> s;
  vector<int> ret;//存放已经遍历好的数组
  if (!root) {
    return ret;
  }
  s.push(root);
  while (!s.empty()) {
    TreeNode* tmp = s.top();
    s.pop();
    ret.push_back(tmp->val);
    if (tmp->right) {
      s.push(tmp->right);
    }
    if (tmp->left) {
      s.push(tmp->left);
    }
  }
  return ret;
}
//使用栈进行后序遍历
vector<int> postorder(TreeNode* root) {
  vector<int> tmp;
  if (!root) return tmp;
  stack<TreeNode*> s;
  s.push(root);
  while (!s.empty()) {
    TreeNode* node = s.top();
    s.pop();
    tmp.push_back(node->val);
    if (node->left) s.push(node->left);
    if (node->right) s.push(node->right);
  }
  reverse(tmp.rbegin(), tmp.rend());
  return tmp;
}
//使用栈进行中序遍历
vector<int> inorder2(TreeNode* root) {
  vector<int> tmp;
  if (!root) return tmp;
  TreeNode* cur = root;
  stack<TreeNode*> s;
  while (cur || !s.empty()) {
    if (cur) {
      s.push(cur);
      cur = cur->left;
    }
    else {
      cur = s.top();
      s.pop();
      tmp.push_back(cur->val);
      cur = cur->right;
    }
  }
  return tmp;
}