二叉树的递归先序中序后序遍历以及非递归层次遍历

1. 二叉树的递归先序遍历：

先访问根节点，然后遍历左子树，最后遍历右子树。

代码实现：

void preOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->val << " ";  // 访问根节点
    preOrder(root->left);     // 遍历左子树
    preOrder(root->right);    // 遍历右子树
}

2. 二叉树的递归中序遍历：

先遍历左子树，然后访问根节点，最后遍历右子树。

代码实现：

void inOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inOrder(root->left);      // 遍历左子树
    cout << root->val << " "; // 访问根节点
    inOrder(root->right);     // 遍历右子树
}

3. 二叉树的递归后序遍历：

先遍历左子树，然后遍历右子树，最后访问根节点。

代码实现：

void postOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postOrder(root->left);    // 遍历左子树
    postOrder(root->right);   // 遍历右子树
    cout << root->val << " "; // 访问根节点
}

4. 二叉树的非递归层次遍历：

使用一个队列来存储每一层的节点，先将根节点入队，然后遍历队列中的元素，将每个元素的左右子节点入队，直到队列为空。

代码实现：

void levelOrder(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);
        }
    }
}