使用堆栈迭代地遍历C二进制搜索树的后序遍历

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

// 二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

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

// 后序遍历二叉树（堆栈迭代）
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    int top = -1;
    struct TreeNode* prev = NULL;
    struct TreeNode* curr = root;
    int* result = (int*)malloc(sizeof(int) * 1000);
    int count = 0;

    while (curr != NULL || top != -1) {
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }

        curr = stack[top];

        // 如果当前节点的右子节点为空或已经访问过，则可以访问当前节点
        if (curr->right == NULL || curr->right == prev) {
            result[count++] = curr->val;
            prev = curr;
            top--;
            curr = NULL;
        } else {
            curr = curr->right;
        }
    }

    free(stack);
    *returnSize = count;
    return result;
}

int main() {
    // 创建二叉搜索树
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(6);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right->left = createNode(5);
    root->right->right = createNode(7);

    int size;
    int* result = postorderTraversal(root, &size);

    printf("后序遍历结果：");
    for (int i = 0; i < size; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
    return 0;
}