前序遍历二叉树的递归算法 中序遍历二叉树的递归算法 层序遍历二叉树的递归算法

前序遍历二叉树的递归算法：

1. 如果根节点为空，则返回。
2. 访问根节点。
3. 对根节点的左子树进行前序遍历。
4. 对根节点的右子树进行前序遍历。

代码实现：

void preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}

中序遍历二叉树的递归算法：

1. 如果根节点为空，则返回。
2. 对根节点的左子树进行中序遍历。
3. 访问根节点。
4. 对根节点的右子树进行中序遍历。

代码实现：

void inorderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}

层序遍历二叉树的递归算法：

层序遍历一般使用队列实现，递归实现效率低且不太方便，下面是非递归代码实现。

void levelOrderTraversal(TreeNode* root) {
if (root == nullptr) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
}

注意：这里的层序遍历使用了 BFS 的思想，所以需要使用队列。