c语言用深度搜索和栈来遍历树的问题

Question

用深度搜索遍历树，原题如下：

我的代码如下：

为了让各路大沈们能更好的理解我的问题，我举一个例子表达我的问题所在：

在这个例子中，我第一条路探索的自然是1->2->6->5->7->9->NULL，然后7->9被标记探索过了，但是最短路径是1->4->7->9->NULL，所以不可能得到正确答案
而且我在洛谷评测结果是RE，而不是WA，这就让我更不能理解了！快帮帮我，我快受不了了！（┬＿┬）(ಥ_ಥ)(｡ŏ_ŏ)

Answer 1

【以下回答由 GPT 生成】

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

#define MAX_TREE_SIZE 100

typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

typedef struct Stack {
    TreeNode* data[MAX_TREE_SIZE];
    int top;
} Stack;

// 初始化栈
void init(Stack* s) {
    s->top = -1;
}

// 入栈
void push(Stack* s, TreeNode* node) {
    if (s->top == MAX_TREE_SIZE - 1) {
        printf("Stack overflow\n");
        exit(1);
    }
    s->data[++(s->top)] = node;
}

// 出栈
TreeNode* pop(Stack* s) {
    if (s->top == -1) {
        printf("Stack underflow\n");
        exit(1);
    }
    return s->data[(s->top)--];
}

// 深度搜索遍历树
void dfsTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack s;
    init(&s);
    push(&s, root);
    while (s.top != -1) {
        TreeNode* node = pop(&s);
        printf("%d ", node->value);
        if (node->right) {
            push(&s, node->right);
        }
        if (node->left) {
            push(&s, node->left);
        }
    }
}

// 示例
int main() {
    // 构建示例树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->value = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->value = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->value = 3;
    root->right->left = NULL;
    root->right->right = NULL;

    // 深度搜索遍历树
    printf("深度搜索遍历结果：");
    dfsTraversal(root);

    return 0;
}

希望这段代码能帮助你解决遍历树的问题。如果还有其他问题，欢迎继续询问！

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^