试编写一个函数，返回一棵给定二叉树在中序遍历下的最后一个结点。用C语言写

在C语言中，你可以编写一个递归函数来找到二叉树中序遍历的最后一个节点。假设我们有一个简单的二叉树结构定义：

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

TreeNode* findLastNodeInInorder(TreeNode* root) {
    if (root == NULL) return NULL; // 如果根节点为空，直接返回

    // 递归查找左子树的最右节点
    TreeNode* lastNodeLeft = findLastNodeInInorder(root->left);

    // 如果左子树非空，返回当前节点，因为中序遍历左子树后会访问根节点
    if (lastNodeLeft != NULL) return root;

    // 否则，返回右子树的最右节点，即为中序遍历的最后一个节点
    return findLastNodeInInorder(root->right);
}

这个`findLastNodeInInorder`函数的工作原理是首先检查根节点是否为空，然后对左子树进行递归查找。如果左子树有节点，则说明最后一个节点在左子树中，所以返回当前节点。如果左子树为空，那么最后一个节点肯定在右子树中，因此继续递归寻找右子树的最右节点。

相关问题

用c语言编写两个函数，返回一棵给定二叉树在中序遍历下的第一个结点和最后一个结点

好的，下面是两个函数的 C 语言实现：

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

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

void first_last_node(struct TreeNode* root, struct TreeNode** first, struct TreeNode** last) {
    if (!root) {
        *first = *last = NULL;
        return;
    }
    *first = *last = root;
    while ((*first)->left) {
        *first = (*first)->left;
    }
    while ((*last)->right) {
        *last = (*last)->right;
    }
}

void first_last_node_recursive_helper(struct TreeNode* node, struct TreeNode** first, struct TreeNode** last) {
    if (!node) {
        return;
    }
    first_last_node_recursive_helper(node->left, first, last);
    if (!(*first)) {
        *first = node;
    }
    *last = node;
    first_last_node_recursive_helper(node->right, first, last);
}

void first_last_node_recursive(struct TreeNode* root, struct TreeNode** first, struct TreeNode** last) {
    *first = *last = NULL;
    first_last_node_recursive_helper(root, first, last);
}

其中，`first_last_node` 是迭代实现，`first_last_node_recursive` 是递归实现。两个函数的时间复杂度均为 $O(n)$，其中 $n$ 是二叉树的结点数。

需要注意的是，函数的返回值是通过指针参数传递的。上面的代码中，`first` 和 `last` 都是 `struct TreeNode*` 类型的指针，传递进去后，函数内部通过修改指针指向的内存地址来返回值。在调用函数时，需要先声明两个指针变量，然后将它们的地址传递给函数，如下所示：

struct TreeNode* root = ... // 二叉树的根节点
struct TreeNode* first, *last;
first_last_node(root, &first, &last);
printf("First node: %d\n", first->val);
printf("Last node: %d\n", last->val);

用C语言写一个分别采用递归和非递归方式编写两个函数，求一棵给定二叉树中叶子结点的个数的代码

当我们用C语言编写一个函数来求一棵给定二叉树中叶子节点的个数时，可以分别采用递归和非递归的方式实现。

1. 递归方式：
递归方式是通过不断地调用函数自身来实现的。对于二叉树的叶子节点个数的求解，可以使用以下递归函数：

// 定义二叉树结点的结构体
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 递归函数，用于求解二叉树中叶子节点的个数
int countLeafNodes(struct TreeNode* root) {
    // 如果当前节点为空，则返回0
    if (root == NULL) {
        return 0;
    }
    // 如果当前节点没有左子树和右子树，则为叶子节点，返回1
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    // 递归地计算左子树和右子树中叶子节点的个数，并返回它们的和
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

2. 非递归方式：
非递归方式是通过使用辅助数据结构（如栈或队列）来实现的。对于二叉树的叶子节点个数的求解，可以使用以下非递归函数：

// 非递归函数，用于求解二叉树中叶子节点的个数
int countLeafNodes(struct TreeNode* root) {
    // 如果根节点为空，则返回0
    if (root == NULL) {
        return 0;
    }
    int count = 0;
    struct TreeNode* stack[100];  // 定义一个栈，用于存储待处理的节点
    int top = -1;  // 栈顶指针初始化为-1
    stack[++top] = root;  // 将根节点入栈
    while (top >= 0) {
        struct TreeNode* node = stack[top--];  // 弹出栈顶节点
        // 如果当前节点没有左子树和右子树，则为叶子节点，计数器加1
        if (node->left == NULL && node->right == NULL) {
            count++;
        }
        // 如果当前节点有右子树，则将右子树入栈
        if (node->right != NULL) {
            stack[++top] = node->right;
        }
        // 如果当前节点有左子树，则将左子树入栈
        if (node->left != NULL) {
            stack[++top] = node->left;
        }
    }
    return count;
}