题解 | #二叉树的下一个结点#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
struct Node{
    struct TreeLinkNode* tree;
    struct Node* next;
};
 
struct sNode{
    struct Node* rear;
};
 
struct sNode *createStack(){
    struct sNode* tmp;
    tmp = (struct sNode*)malloc(sizeof(struct sNode));
    tmp->rear = NULL;
    return tmp;
}
 
bool isEmpty(struct sNode* tmp){
    if(tmp->rear == NULL)return true;
    else return false;
}
 
void sPush(struct sNode* tmp, struct TreeLinkNode* tree){
    if(!tmp)tmp=createStack();
    struct Node* tmpNode;
    tmpNode = (struct Node*)malloc(sizeof(struct Node));
    tmpNode->tree = tree;
    tmpNode->next = tmp->rear;
    tmp->rear = tmpNode;
}
 
struct TreeLinkNode* sPop(struct sNode* tmp){
    if(isEmpty(tmp))return NULL;
    else{
        struct Node* tmpNode;
        tmpNode = (struct Node*)malloc(sizeof(struct Node));
        struct TreeLinkNode* tmpTree;
        tmpTree = (struct TreeLinkNode*)malloc(sizeof(struct TreeLinkNode));
        tmpNode = tmp->rear;
        tmpTree = tmpNode->tree;
        tmp->rear = tmpNode->next;
        free(tmpNode);
        return tmpTree;
    }
}
//-------------------------------------------------------------//
int* inorderTraversal(struct TreeNode* root, int* returnSize ) {
    // write code here
    struct sNode* stack;
    stack = createStack();
    int *result;
    result = (int*)malloc(sizeof(int) * 1000);
    struct TreeLinkNode* tmp = root;
    int i = 0;
    while(tmp || !isEmpty(stack)){
        while(tmp){
            sPush(stack, tmp);
            tmp = tmp->left;
        }
        if(!isEmpty(stack)){
            tmp = sPop(stack);
            result[i] = tmp->val;
            i += 1;
            tmp = tmp->right;
        }
    }
    *returnSize = i;
    return result;
}
//-------------------------------------------------------------//