一.递归

递归很简单，只要在调用子节点前对当前节点进行操作即可

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};void dfs(TreeNode *root, vector<int> &arr){if(!root){return;}arr.emplace_back(root->val);dfs(root->left, arr);dfs(root->right, arr);
}

二.显示栈迭代

递归是把栈给隐藏起来，如果需要用迭代的方法，可以建立一个栈来实现遍历
思路是：
1.若有可进栈节点则进栈，否则出栈
2.栈顶元素的是否有左孩子节点有则进栈，循环直到没有
3.如果栈顶元素有右孩子节点，则赋值给insert，下次循环时进栈。
一直循环下去直到没有节点为止

vector<int> preorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode *> st;TreeNode *insert = root;while(insert || !st.empty()){if(insert){		// 有可进栈的节点st.push(insert);res.emplace_back(insert->val);	// 是前序遍历，进栈前记录数据（和递归一样）while(st.top()->left){	// 不断获取左孩子节点st.push(st.top()->left);res.emplace_back(st.top()->val);}// insert = nullptr;}else{st.pop();	// 没有可插入的节点就出栈（这样可以获取更上一层的节点）}if(!st.empty() && st.top()->right){insert = st.top()->right;	// 有右孩子节点，就赋值等下次循环插入st.pop();	// 这里必须出栈，否则会重复遍历}else{insert = nullptr;}}return res;
}

三.morris遍历

morris遍历的优点在于，只需用到常量级的空间消耗就可实现遍历
大致思路：
访问A的时候，要建立 A的左子树与A的联系，去B的最右右节点即E，设 E->right =A,
如此当访问完A的左子树时，可以返回到A节点。
同理 访问B时， 会建立 D->right = B (D没有右节点，所以时本身)

void printTree(TreeNode* root) {if (!root)return;TreeNode* pre;vector<int> res;while (root) {if (!root->left) {	// 没有左孩子节点，记录数据，调到右孩子节点res.emplace_back(root->val);	root = root->right;continue;}pre = root->left;while (pre->right && pre->right != root) {	// 获取左子树的最右子节点pre = pre->right;}if (!pre->right) {		// 不存在则时第一次遍历res.emplace_back(root->val);pre->right = root;root = root->left;}else {	// 存在则是第二次，需要返回上一个层次pre->right = nullptr;root = root->right;}}
}

备注：
morris遍历的前序和中序遍历非常思路一致，唯一的不同在于，记录数据的位置，如上段代码，改成如下就成了中序遍历：

		if (!pre->right) {		// 不存在则时第一次遍历//res.emplace_back(root->val); //前序便历在这里记录pre->right = root;root = root->left;}else {	// 存在则是第二次，需要返回上一个层次pre->right = nullptr;res.emplace_back(root->val);	//中序便历在这里记录root = root->right;}

想详细了解morris遍历的，可以看下我写的morris中序遍历。