面试题：C语言二叉树的深度优先搜索优化

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

struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 优化思路：使用栈来模拟递归，减少递归调用次数，从而优化性能和内存使用
// 栈节点结构
struct StackNode {
    struct TreeNode* treeNode;
    struct StackNode* next;
};

// 入栈操作
void push(struct StackNode** top, struct TreeNode* newNode) {
    struct StackNode* newStackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    newStackNode->treeNode = newNode;
    newStackNode->next = *top;
    *top = newStackNode;
}

// 出栈操作
struct TreeNode* pop(struct StackNode** top) {
    if (*top == NULL) return NULL;
    struct StackNode* temp = *top;
    struct TreeNode* poppedNode = temp->treeNode;
    *top = (*top)->next;
    free(temp);
    return poppedNode;
}

// 检查栈是否为空
int isStackEmpty(struct StackNode* top) {
    return top == NULL;
}

// 深度优先搜索（DFS）
void DFS(struct TreeNode* root) {
    struct StackNode* stackTop = NULL;
    push(&stackTop, root);

    while (!isStackEmpty(stackTop)) {
        struct TreeNode* current = pop(&stackTop);
        printf("%d ", current->data);

        if (current->right) push(&stackTop, current->right);
        if (current->left) push(&stackTop, current->left);
    }
}

// 创建新节点
struct TreeNode* createNode(int data) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("DFS Traversal: ");
    DFS(root);

    return 0;
}

优化思路：

使用栈模拟递归：传统的DFS使用递归，递归过程会消耗栈空间，每次递归调用都需要保存当前函数的上下文，调用次数过多可能导致栈溢出。通过使用栈数据结构来模拟递归过程，手动管理节点的访问顺序，减少了系统栈的使用，从而减少递归调用次数和优化内存使用。
内存管理优化：在使用栈时，对于栈节点的内存分配和释放进行了合理管理，确保不会出现内存泄漏。同时，在二叉树节点的创建和使用过程中，也合理分配和释放内存。

面试题：C语言二叉树的深度优先搜索优化

知识考点

面试题答案