求位于先序序列中第k 个位置的结点的值

问题：求位于先序序列中第k 个位置的结点的值

【问题描述】求位于先序序列中第k 个位置的结点的值

【输入形式】先序序列构造二叉树，结点数据类型为字符型，空结点用'#'表示。以及结点的序列值k

【输出形式】输出第k个结点的值

【样例输入】A B # # C # #

           3

【样例输出】C

【样例说明】对于非法输入的序列值k，则输出ERROR

           比如对于A B # # C # #,其相应的k的合理范围应为1，2，3

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 根据先序序列构造二叉树
TreeNode* buildTree(char** preorder) {
    char* val = *preorder;
    (*preorder)++;
    if (val[0] == '#') {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val[0];
    root->left = buildTree(preorder);
    root->right = buildTree(preorder);
    return root;
}

// 先序遍历二叉树，返回第k个位置的节点值
char findKthNode(TreeNode* root, int k, int* count) {
    if (root == NULL) {
        return '\0';
    }
    (*count)++;
    if (*count == k) {
        return root->val;
    }
    char left_result = findKthNode(root->left, k, count);
    if (left_result != '\0') {
        return left_result;
    }
    char right_result = findKthNode(root->right, k, count);
    if (right_result != '\0') {
        return right_result;
    }
    return '\0';
}

int main() {
    // 输入先序序列和k
    char preorder[100];
    fgets(preorder, sizeof(preorder), stdin);
    int k;
    scanf("%d", &k);

    // 构造二叉树
    char* p = preorder;
    TreeNode* root = buildTree(&p);

    // 初始化计数器
    int count = 0;

    // 查找第k个位置的节点值
    char result = findKthNode(root, k, &count);

    // 输出结果
    if (result != '\0') {
        printf("%c\n", result);
    } else {
        printf("ERROR\n");
    }

    return 0;
}

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 根据先序序列构造二叉树
TreeNode* buildTree() {
    char val;
    scanf(" %c", &val);
    if (val == '#') {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = buildTree();
    root->right = buildTree();
    return root;
}

// 先序遍历二叉树，返回第k个位置的节点值
char findKthNode(TreeNode* root, int k, int* count) {
    if (root == NULL) {
        return '\0';
    }
    (*count)++;
    if (*count == k) {
        return root->val;
    }
    char left_result = findKthNode(root->left, k, count);
    if (left_result != '\0') {
        return left_result;
    }
    char right_result = findKthNode(root->right, k, count);
    if (right_result != '\0') {
        return right_result;
    }
    return '\0';
}

int main() {
    // 构造二叉树
    TreeNode* root = buildTree();

    // 输入k
    int k;
    scanf("%d", &k);

    // 初始化计数器
    int count = 0;

    // 查找第k个位置的节点值
    char result = findKthNode(root, k, &count);

    // 输出结果
    if (result != '\0') {
        printf("%c\n", result);
    } else {
        printf("ERROR\n");
    }

    return 0;
}