leetcode 145: Binary Tree Postorder Traversal

這次的題目是後序遍歷，並回傳一個陣列 只要遞迴地依照左子樹 $\Rightarrow$ 右子樹 $\Rightarrow$ 根節點的順序把值加進 list 就行了

為了遍歷時方便處理，首先寫了一個接 list 的函式

struct ListNode* append(struct ListNode* a, struct ListNode* b)
{
    if(!a) return b;
    if(!b) return a;
    struct ListNode* t = a;
    while(t->next) t = t->next;
    t->next = b;
    return a;
}

接下來是遍歷的主體，8 和 10 行是先接左右子樹，12~15 行是把根節點接上去

struct ListNode* travel(struct TreeNode* rt)
{
    if(!rt) return NULL;

    struct ListNode *ret, *temp;

    // left child
    ret = travel(rt->left);
    // right child
    ret = append(ret, travel(rt->right));
    // append root
    temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = rt->val;
    temp->next = NULL;
    ret = append(ret, temp);

    return ret;
}

然後是解答的部分，首先取得遍歷的 list，然後再計算回傳的陣列大小 之後再依序把 list 的內容放進陣列並且釋放記憶體

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    struct ListNode *list = travel(root);
    struct ListNode *temp = list;
    struct ListNode *temp2;

    // count return size
    int sz = 0;
    while(temp)
    {
        sz++;
        temp = temp->next;
    }

    int* ret = (int*)malloc(sizeof(int) * sz);
    temp = list;
    sz = 0;
    while(temp)
    {
        ret[sz++] = temp->val;
        temp2 = temp;
        temp = temp->next;
        free(temp2);
    }

    *returnSize = sz;

    return ret;
}