一.递归

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

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中序遍历。