144. 二叉樹的前序遍歷
提示：
- 樹中節(jié)點數(shù)目在范圍 [0, 100] 內(nèi)
函數(shù)原型：
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
首先先觀察一下這個函數(shù)原型，TreeNode* root 為形參，傳入根節(jié)點，int* returnSize為形參，在函數(shù)調(diào)用時用于返回改題目所求數(shù)組的長度，因為由于C語言的局限，只能返回一個參數(shù)，所以采用這種通過傳入指針的形參，來改變函數(shù)外部實參的方法。
題目要求給一個二叉樹的根節(jié)點，返回其前序遍歷的數(shù)組。
首先先計算二叉樹的節(jié)點個數(shù)，用于后續(xù)的數(shù)組空間申請。
int TreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
然后先序遍歷，寫入數(shù)組：
因為根據(jù)上述代碼，求得節(jié)點個數(shù)為n，則該數(shù)組一共有n個空間，控制寫入數(shù)組的下標(biāo)需要傳入int* ，因為若直接傳入int，形參的改變不影響實參的改變。文章來源：http://www.zghlxwxcb.cn/news/detail-802267.html
void preorder (struct TreeNode* root, int* a,int* pi)
{
if(root == NULL)
return ;
a[(*pi)++] = root->val;
preorder(root->left,a,pi);
preorder(root->right,a,pi);
}
使用malloc函數(shù)構(gòu)建數(shù)組，返回數(shù)組。文章來源地址http://www.zghlxwxcb.cn/news/detail-802267.html
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int n = TreeSize(root);
int* a = (int*)malloc(sizeof(int)*n);
*returnSize = n;
int* i = 0;
preorder(root,a,&i);
return a;
}
代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int TreeSize(struct TreeNode* root)
{
return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
void preorder (struct TreeNode* root, int* a,int* pi)
{
if(root == NULL)
return ;
a[(*pi)++] = root->val;
preorder(root->left,a,pi);
preorder(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
int n = TreeSize(root);
int* a = (int*)malloc(sizeof(int)*n);
*returnSize = n;
int* i = 0;
preorder(root,a,&i);
return a;
}
到了這里，關(guān)于【C語言題解】 | 144. 二叉樹的前序遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
