Sample code in C


  • 1
    B
    #define DELTA 30
    typedef struct _stackNode {
        struct TreeNode *pTN;
        char mark;
    }stackNode;
    typedef struct _stack {
        stackNode **ppSNS;
        int n, cap;
    }stack;
    stack *initStack ()
    {
        stack *pST;
    
        pST = (stack *)malloc (sizeof (stack));
        memset (pST, 0, sizeof (stack));
    
        return pST;
    }
    stack *pushStack (stack *pST, struct TreeNode *pTN)
    {
        stackNode *pSN;
        if (!pST) pST = initStack ();
        if (pTN) {
            pSN = (stackNode *)malloc (sizeof (stackNode));
            memset (pSN, 0, sizeof (stackNode));
            pSN->pTN = pTN;
            if (pST->n == pST->cap) {
                pST->ppSNS = (stackNode **)realloc (pST->ppSNS, sizeof (stackNode *) * (pST->cap += DELTA));
            }
            pST->ppSNS[pST->n++] = pSN;
        }
    
        return pST;
    }
    stackNode *topStack (stack *pST)
    {
        if (pST && pST->n > 0) {
            return pST->ppSNS[pST->n - 1];
        }
    
        return NULL;
    }
    stackNode *popStack (stack *pST)
    {
        if (pST && pST->n > 0) {
            return pST->ppSNS[--pST->n];
        }
    
        return NULL;
    }
    void freeStack (stack *pST)
    {
        if (pST) {
            if (pST->ppSNS) free (pST->ppSNS);
            free (pST);
        }
    }
    int* postorderTraversal(struct TreeNode* root, int* returnSize)
    {
        stack *pST = NULL;
        stackNode *pSN, *pSTParent;
        int *pIResult = NULL, cap = 0;
    
        *returnSize = 0;
        if (root) {
            pST = pushStack (pST, root);
            while (pST->n) {
                pSN = topStack (pST);
                if (2 == pSN->mark) {//Both left & right branches are visited.
                    popStack (pST);
                    if (*returnSize == cap) {
                        pIResult = (int *)realloc (pIResult, sizeof (int) * (cap += DELTA));
                    }
                    pIResult[(*returnSize)++] = pSN->pTN->val;
                    free (pSN);
                    pSN = NULL;
                    pSTParent = topStack (pST);
                    if (pSTParent) (pSTParent->mark)++;
                } else if (1 == pSN->mark) {//left branch is visited.
                    if (pSN->pTN->right) {
                        pushStack (pST, pSN->pTN->right);
                    } else {
                        (pSN->mark)++;
                    }
                } else {//probe left branch
                    if (pSN->pTN->left) {
                        pushStack (pST, pSN->pTN->left);
                    } else {
                        (pSN->mark)++;
                    }
                }
            }
            freeStack (pST);
        }
    
        return pIResult;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.