二叉树深度优先搜素又可细分为中序遍历、前序遍历、后序遍历，每种遍历方式的代码实现又分别有递归方式和迭代方式。

递归方式的缺点：① 如果二叉树的深度太大，那么递归的代码可能会导致调用栈溢出； ② 代码简单，因此在面试时面试官可能会要求以迭代的方式进行实现，所以3种遍历方式的2种实现方式都需要掌握！

例子

• 中序遍历
  A C B D F H E M G
• 前序遍历
  F C A D B E H G M
• 后序遍历
  A B D C H M G E F

// 基本数据结构
struct TreeNode {
	int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};

中序遍历

递归方式

void inorderTraversal(TreeNode* root) {
    dfs(root);
}

void dfs(TreeNode* root) {
	if(root != nullptr) return ;
    
    dfs(root.left);
    // 对该节点的操作放在两个dfs()函数中间
    cout << root->val << endl;
    dfs(root.right);
}

迭代方式

为了在一个节点被遍历之后能够接着回去遍历它的父节点，可以在顺着指向左子节点的指针遍历二叉树时把遇到的每个节点都添加到一个栈中。当一个节点被遍历之后，就可以从栈中得到它的父节点。

void inorderTraversal(TreeNode* root) {
	stack<TreeNode> my_stack;
    TreeNode* cur = root; // 当前遍历的节点
    while(cur != nullptr || !my_stack.empty()) {
    	while(cur != nullptr) { // 顺着左子节点的指针一直向下移动，并入栈
        	my_stack.push_back(cur);
            cur = cur->left;
        }
        
        // 出栈并遍历，按照中序遍历的顺序，在遍历一个节点后再指向它的右子节点
        cur = my_stack.top();
        my_stack.pop();
        cout << cur->val << endl;
        cur = cur->right;
    }
}

前序遍历

递归方式

前序的递归代码和中序的递归代码类似。

void preorderTraversal(TreeNode* root) {
    dfs(root);
}

void dfs(TreeNode* root) {
	if(root != nullptr) return ;
    
    // 对该节点的操作放在两个dfs()函数前面
    cout << root->val << endl;
    dfs(root.left);
    dfs(root.right);
}

迭代方式

前序的递归代码和中序的递归代码也类似。

void preorderTraversal(TreeNode* root) {
	stack<TreeNode> my_stack;
    TreeNode* cur = root; // 当前遍历的节点
    while(cur != nullptr || !my_stack.empty()) {
    	while(cur != nullptr) { 
        	cout << cur->val << endl;
        	my_stack.push_back(cur);
            cur = cur->left;
        }
        
        cur = my_stack.top();
        my_stack.pop();
        cur = cur->right;
    }
}

后序遍历

递归方式

void postorderTraversal(TreeNode* root) {
    dfs(root);
}

void dfs(TreeNode* root) {
	if(root != nullptr) return ;
    
    dfs(root.left);
    dfs(root.right);
    // 对该节点的操作放在两个dfs()函数后面
    cout << root->val << endl;
}

迭代方式

与中序遍历、前序遍历相比，后续遍历的迭代代码要稍微复杂一点。当达到某个节点时，如果之前还没有遍历过它的右子树就得前往它的右子节点，如果之前已经遍历过它的右子树那么就可以遍历这个节点。也就是说，此时要根据它的右子树此前有没有遍历过来确定是否应该遍历当前的节点。如果此前右子树已经遍历过，那么在右子树中最后一个遍历的节点应该是右子树的根节点，也就是当前节点的右子节点。可以记录遍历的前一个节点。如果一个节点存在右子节点并且右子节点正好是前一个被遍历的节点，那么它的右子树已经遍历过，现在是时候遍历当前的节点了。

void postorderTraversal(TreeNode* root) {
	stack<TreeNode> my_stack;
    TreeNode* cur = root; // 当前遍历的节点
    TreeNode* prev = nullptr; // 遍历过的前一个节点，初始化为null
    while(cur != nullptr || !my_stack.empty()) {
    	while(cur != nullptr) { 
        	my_stack.push_back(cur);
            cur = cur->left;
        }
        
        cur = my_stack.top();
        if(cur->right != nullptr && cur->right != prev) {
        	cur = cur->right;
        } else {
        	my_stack.pop();
            cout << cur->val << endl;
            prev = cur;
            cur = nullptr;
        }
    }
}

总结

无论是哪种深度优先算法，也不管是递归方式还是迭代方式，如果二叉树有 n 个节点，那么它们的时间复杂度都是O(n)。如果二叉树的深度为 h ，那么它们的空间复杂度都是O(h)。在二叉树中，二叉树的深度h的最小值是 $log_2(n+1)$ ，最大值为 n。