TOP101题解 | BM24#二叉树的中序遍历#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @author Senky
 * @date 2023.05.06
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 
 *  这题数据规模就变成了1000了,递归调用肯定不可取的(时间限制1s),只能用栈来操作了
 *  已经用线性栈,并且案例通过了,但是想用更常见一点的链栈来操作，核心代码就是左子树入栈
 * @param root TreeNode类 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

/*栈的每一个元素是一个指向叶子结点的指针*/
struct StackNode
{
    struct TreeNode* tree_node; 
    struct StackNode* next;
};

/*栈顶指针*/
struct Stack
{
    struct StackNode* bottom;
    struct StackNode* top;
    int length;
};

/*判断栈是否为空*/
bool StackIsEmpty(struct Stack* stack)
{
    return (stack->top == NULL);
}

//创建空栈
struct Stack* StackCreat()
{
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->bottom = NULL;
    stack->top = NULL;
    stack->length = 0;

    return stack;
}

/*入栈*/
void StackPUSH(struct Stack* stack,struct TreeNode* tree_Node)
{
    struct StackNode* stack_newnode = (struct StackNode*)malloc(sizeof(struct StackNode));
    stack_newnode->tree_node = tree_Node;
    stack_newnode->next = NULL;

    if(StackIsEmpty(stack))
    {
        stack->top = stack->bottom =  stack_newnode;
    }
    else
    {
        stack->top->next = stack_newnode;
        stack->top = stack_newnode;    
    }

    stack->length++;
}

/*出栈*/
struct TreeNode* StackPOP(struct Stack* stack)
{
    if(StackIsEmpty(stack))
    {
        return NULL;
    }

    struct StackNode* temp = stack->top;
    struct TreeNode* tree_node = stack->top->tree_node; 

    if(stack->length == 1)
    {
        stack->top = stack->bottom = NULL;
    }
    else 
    {
        struct StackNode* target = stack->bottom;
        while(target->next != stack->top) target = target->next;

        target->next = NULL;
        stack->top = target;
    }

    stack->length--;

    free(temp);
    return tree_node;

}


int* inorderTraversal(struct TreeNode* root, int* returnSize ) 
{
    // write code here
    struct Stack* stack = StackCreat();
    int* result = (int*)calloc(1000,sizeof(int));
    *returnSize = 0;

    //左子树入栈
     while(!StackIsEmpty(stack) || root != NULL)
    {
        /*根结点不为空则*/
        while(root != NULL)
        {
            StackPUSH(stack,root);
            root = root->left;
        }
 
        /*将最后一个没有左孩子的结点出栈*/
        if(!StackIsEmpty(stack))
        {  
            root = StackPOP(stack);
            result[(*returnSize)++] = root->val;
 
            /*将root指向右子树,再对右子树进行栈操作*/
            root = root->right;
        }
    }

   return result;

}