题目要求输出中缀表达式，对应表达式树（二叉树）的中序遍历序列。但本题难点在于要输出左右括号，所以也融合了二叉树的前序遍历和后序遍历，二叉树的前序遍历、中序遍历、后序遍历本质都是深度优先搜索。

深度优先搜索

递归遍历

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
    char data[10];   // 存储操作数或操作符
    struct node *left, *right;
}BTree;

void dfs(BTree* root) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {  // 如果只有一个数那么不需要加括号
        printf("%s", root->data);
    } else {
        printf("(");
        dfs(root->left);
        printf("%s", root->data);
        dfs(root->right);
        printf(")");
    }
}

void expressionTree(BTree* root) {
    if(root == NULL) return;
    dfs(root->left);
    printf("%s", root->data);
    dfs(root->right);
    return;
}

BTree *createBinaryTree(char a[][10], int n) {
    if (strcmp(a[0], "null") == 0) {
        return NULL;
    }
    int i = 0;
    BTree *root = (struct node*)malloc(sizeof(struct node));
    strcpy(root->data, a[i++]);
    root->left = NULL;
    root->right = NULL;
    struct node** que = (struct node**)malloc(sizeof(struct node*));
    int front = 0, rear = 0;
    BTree *curr = root;
    que[rear++] = curr;
    while (front < rear && i < n) {
        curr = que[front++];
        for (int j = 0; j < 2 && i < n; j++, i++) {
            if (strcmp(a[i], "null") != 0) {
                if (j == 0) {
                    curr->left = (struct node*)malloc(sizeof(struct node));
                    strcpy(curr->left->data, a[i]);
                    curr->left->left = NULL;
                    curr->left->right = NULL;
                    que[rear++] = curr->left;
                } else {
                    curr->right = (struct node*)malloc(sizeof(struct node));
                    strcpy(curr->right->data, a[i]);
                    curr->right->left = NULL;
                    curr->right->right = NULL;
                    que[rear++] = curr->right;
                }
            }
        }
    }
    return root;
}

int main() {
    char a[][10] = {"*", "+", "*", "a", "b", "c", "-", "null", "null", "null", "null", "null", "null", "null", "d"};
    expressionTree(createBinaryTree(a, 15));
    return 0;
}

复杂度分析

• 时间复杂度： O(n) ，其中 n 为二叉树的结点个数。二叉树的每个结点最多被访问三次，因此时间复杂度为 O(n) 。
• 空间复杂度： O(n) ，其中 n 为二叉树的结点个数。递归栈最深为 n ，因此需要额外的 O(n) 的空间。