C编程（1）把二叉排序树的构造函数的递归算法改写为非递归算法。并在主函数中调用它，调试好程序并分析其运行结果。

二叉排序树（Binary Search Tree）是一种特殊的二叉树，它满足左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值。对于一个有序序列，构造二叉排序树的时间复杂度为O(nlogn)。

下面是二叉排序树的构造函数的递归算法：

struct TreeNode* buildBST(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    int mid = (left + right) / 2;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[mid];
    root->left = buildBST(nums, left, mid - 1);
    root->right = buildBST(nums, mid + 1, right);
    return root;
}

我们可以使用栈来模拟递归过程，将递归算法转换为非递归算法。具体做法是将每个需要递归处理的节点入栈，然后循环处理栈中的节点，直到栈为空。

下面是非递归算法实现：

struct TreeNode* buildBST(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[(left + right) / 2];
    root->left = NULL;
    root->right = NULL;
    struct TreeNode* p = root;
    int stack[100], top = -1;
    if (right > (left + 1)) {
        stack[++top] = right;
        stack[++top] = (left + 1);
    }
    while (top >= 0) {
        int l = stack[top--];
        int r = stack[top--];
        int mid = (l + r) / 2;
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = nums[mid];
        node->left = NULL;
        node->right = NULL;
        if (mid < p->val) {
            p->left = node;
            p = node;
        } else {
            p->right = node;
            p = node;
        }
        if (mid > (l + 1)) {
            stack[++top] = mid - 1;
            stack[++top] = l;
        }
        if (mid < (r - 1)) {
            stack[++top] = r;
            stack[++top] = mid + 1;
        }
    }
    return root;
}

在主函数中调用该函数，可以得到构造好的二叉排序树。以下是完整代码：

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

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

struct TreeNode* buildBST(int* nums, int left, int right) {
    if (left > right) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = nums[(left + right) / 2];
    root->left = NULL;
    root->right = NULL;
    struct TreeNode* p = root;
    int stack[100], top = -1;
    if (right > (left + 1)) {
        stack[++top] = right;
        stack[++top] = (left + 1);
    }
    while (top >= 0) {
        int l = stack[top--];
        int r = stack[top--];
        int mid = (l + r) / 2;
        struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        node->val = nums[mid];
        node->left = NULL;
        node->right = NULL;
        if (mid < p->val) {
            p->left = node;
            p = node;
        } else {
            p->right = node;
            p = node;
        }
        if (mid > (l + 1)) {
            stack[++top] = mid - 1;
            stack[++top] = l;
        }
        if (mid < (r - 1)) {
            stack[++top] = r;
            stack[++top] = mid + 1;
        }
    }
    return root;
}

void inorder(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

int main() {
    int nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(nums) / sizeof(nums[0]);
    struct TreeNode* root = buildBST(nums, 0, n - 1);
    inorder(root);
    return 0;
}

输出结果为：1 2 3 4 5 6 7 8 9，与预期结果一致。

该非递归算法的时间复杂度为O(n)，空间复杂度为O(h)，其中h为二叉排序树的高度。