1、递归建立二叉树； 2、先序递归遍历二叉树； 3、中序递归遍历二叉树； 4、后序递归遍历二叉树。 5、中序非递归遍历二叉树 用C++语言

1. **递归建立二叉树**：
递归构建二叉树通常涉及到两个步骤：创建节点并将其左子树和右子树设置为其他递归调用的结果。例如，对于一个整数`val`，你可以这样定义：

   struct TreeNode {
       int val;
       TreeNode* left;
       TreeNode* right;
       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   };

   // 递归函数示例
   TreeNode* buildTree(int arr[], int start, int end) {
       if (start > end)
           return nullptr;
       int mid = (start + end) / 2;
       TreeNode* root = new TreeNode(arr[mid]);
       root->left = buildTree(arr, start, mid - 1);
       root->right = buildTree(arr, mid + 1, end);
       return root;
   }

2. **先序递归遍历二叉树**：
先序遍历顺序为根节点 -> 左子树 -> 右子树。C++实现如下：

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

3. **中序递归遍历二叉树**：
中序遍历顺序为左子树 -> 根节点 -> 右子树：

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

4. **后序递归遍历二叉树**：
后序遍历顺序为左子树 -> 右子树 -> 根节点：

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

5. **中序非递归遍历二叉树（使用栈）**：
使用迭代法（栈）实现中序遍历，避免了递归带来的额外开销：

   void inorderTraversalNonRecursive(TreeNode* root) {
       stack<TreeNode*> s;
       TreeNode* current = root;

       while (current != nullptr || !s.empty()) {
           while (current != nullptr) {
               s.push(current);
               current = current->left;
           }
           current = s.top();
           s.pop();
           cout << current->val << " ";
           current = current->right;
       }
   }