一、递归

1.1 前序遍历

void preprder(TreeNode* root, vector<int> &ans) {
	if(root == nullptr) return;
	ans.push_back(root -> val);
	pre(root -> left, ans);
	pre(root -> right, ans);
}

1.2 中序遍历

void inorder(TreeNode* root, vector<int> &ans) {
	if(root == nullptr) return;
	pre(root -> left, ans);
	ans.push_back(root -> val);
	pre(root -> right, ans);
}

1.3 后序遍历

void inorder(TreeNode* root, vector<int> &ans) {
	if(root == nullptr) return;
	pre(root -> left, ans);
	pre(root -> right, ans);
	ans.push_back(root -> val);
}

二、迭代

2.1 前序遍历

vector<int> preorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(root == nullptr) return ans;
	stack<TreeNode*> stk;//保存迭代过程中指向节点的指针。用途：遇空节点时返回上一个节点
	while(!stk.empty() || root != nullptr) {
		while(root != nullptr) { //一直往左子树搜索
			ans.push_back(root->val);//访问当前root指向的节点
			stk.push(root);//保留返回的路径，注意栈中的元素均已被访问
			root = root -> left;
		}
		//循环结束，root指空，stk.top()指向当前子树最左面节点
		root = stk.top();
		//stk.top()指向的节点已经被访问过了
		//stk.top()节点的左子树所有节点已经均被访问，所以删除栈顶元素
		stk.pop();
		//前序遍历：根，左，右, 所以接下来向右子树迭代
		root = root -> right;//向右子树迭代
	}
	return ans;
}

2.2 中序遍历

vector<int> inorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(root == nullptr) return ans;
	stack<TreeNode*> stk;
	while (root != nullptr || !stk.empty()) {
		while (root != nullptr) {
			//ans.push_back(root -> val); 注意与先序遍历的差别
			stk.push(root);
			root = root->left;
		}
		root = stk.top();
		stk.pop();
		//在前序遍历中，下面一行代码在上方的循环中
		ans.push_back(root->val);//中序遍历：左，根，右。
		root = root->right;
	}
	return ans;
}

2.3 后序遍历

2.3.1 方法一

vector<int> postorderTraversal(TreeNode *root) {
	vector<int> ans;
	if (root == nullptr) {
		return ans;
	}
	stack<TreeNode*> stk;
	TreeNode *prev = nullptr;//指向最近访问的节点
	while (root != nullptr || !stk.empty()) {
		while (root != nullptr) {
			stk.push(root);
			root = root->left;
		}
		root = stk.top();//root指向最左边的结点
		stk.pop();//结点出栈
		//后序遍历：左，右，根
		//如果右结点为空，或右结点已经被访问，则访问该节点
		if (root->right == nullptr || root->right == prev) {
			ans.push_back(root->val);//右结点空，则访问目前结点
			prev = root;//prev记录最近访问的节点
			root = nullptr;//置空，防止下次循环指针入栈
		} else {//还有右结点
			stk.push(root);//根节点重新入栈
			root = root->right;//迭代右子树
		}
	}
	return res;
}

2.3.2 方法二

用一个辅助栈记录访问路径。后序遍历，树中每一个节点需要进栈三次，出栈三次，第一次出栈是遍历节点左子树，第二次出栈是遍历节点右子树，第三次出栈是访问节点。

vector<int> postorderTraversal(TreeNode* root) {
	vector<int> ans;
	if(root == nullptr) return ans;
	stack<pair<TreeNode*,int>> stk;//pair<TreeNode*,int>，second记录进栈次数
	stk.push({root, 0});//根节点进栈
	while(!stk.empty()) {
		pair<TreeNode*,int> p = stk.top();//出栈
		stk.pop();//节点出栈
		if(p.second == 0) {//节点第一次出栈，访问其左子树
			stk.push({p.first, 1});//原节点进栈，修改进出栈记录，0->1
			if(p.first->left != nullptr) {
				stk.push({p.first->left, 0});//左子节点进栈,准备遍历其左子树
			}
		}
		if(p.second == 1) {//节点第二次出栈，访问其右子树
			stk.push({p.first, 2});
			if(p.first->right != nullptr) {
				stk.push({p.first->right, 0});
			}
		}
		if(p.second == 2) {//节点第三次出栈，访问该节点
			ans.push_back(p.first->val);//访问节点
		}
	}
	return ans;
}

三、层序遍历

vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> ans;
	vector<int> tmp;//保留每一层的元素
	if(root == nullptr) return ans;
	queue<TreeNode*> q;
	q.push(root);
	tmp.push_back(root->val);//保留第零层元素
	//int level = 0; 当前处于第0层
	while(!q.empty()) {
		ans.push_back(tmp);//当前层元素均保留在了tmp中
		//level++; 进入下一层
		int currentSize = q.size();//当前层元素个数
		tmp.clear();//清空当前层元素，以便记录下一层元素
		for(int i = 0; i < currentSize; i++) { //遍历当层所有元素
			TreeNode* p = q.front();
			q.pop();//元素出队
			if(p->left != nullptr) {
				q.push(p->left);//下层的元素入队
				tmp.push_back(p->left->val);//记录下层元素
			}
			if(p->right != nullptr) {
				q.push(p->right);
				tmp.push_back(p->right->val);
			}
		}
	}
	return ans;
}