[leetcode]Binary Tree Preorder Traversal

Question :

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,2,3].

Explain :

　　　　寫一個int* preorderTraversal(struct TreeNode* root, int* returnSize) 。

　　　　要把traversal的結果，輸出一個array. 回傳array的head pointer. 但是array size怎辦呢?

　　　　因為C一次只能回傳一個value. 這裡我們只好用call by address的方式，讓leetcode知道array size.

Code :

　　Recursive solution

int totalNodes(struct TreeNode* root) {
    if (!root) return 0;
    return 1+totalNodes(root->left)+totalNodes(root->right);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = totalNodes(root);
    int* rv = (int*)malloc(*returnSize*sizeof(int));
    void _preorderTraversal(struct TreeNode* root, int** rv){
        if(root) {
            **rv = root->val;
            (*rv)++;
            _preorderTraversal(root->left, rv);
            _preorderTraversal(root->right, rv);
        }
    }
    int* tmp = rv;
    _preorderTraversal(root, &rv);
    return tmp;
}

心得 : 一開始沒想到竟然要用到pointer of pointer. 來傳pointer address

　　若是不用的話，我之前的程式。

　　　會在以下這個case出錯。

　　　　/ \

　　　1 　　 2

[leetcode]Binary Tree Preorder Traversal

推荐阅读