朋友們、伙計(jì)們，我們又見(jiàn)面了，本期來(lái)給大家解讀一下LeetCode中第144道二叉樹(shù)OJ題，如果看完之后對(duì)你有一定的啟發(fā)，那么請(qǐng)留下你的三連，祝大家心想事成！

數(shù)據(jù)結(jié)構(gòu)與算法專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)與算法

個(gè)? 人? 主? 頁(yè)?：stackY、

C 語(yǔ) 言 專(zhuān) 欄：C語(yǔ)言：從入門(mén)到精通

?LeetCode--144.二叉樹(shù)的前序遍歷：https://leetcode.cn/problems/binary-tree-preorder-traversal/

目錄

1.題目介紹

2.實(shí)例演示

3.解題思路

#二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)?

#將二叉樹(shù)結(jié)點(diǎn)的值保存在數(shù)組中?

完整代碼：

1.題目介紹

給你二叉樹(shù)的根節(jié)點(diǎn)?root?，返回它節(jié)點(diǎn)值的?前序?遍歷。

2.實(shí)例演示

3.解題思路

本道題的意思要將前序遍歷的結(jié)果儲(chǔ)存在一個(gè)數(shù)組中，而這個(gè)數(shù)組需要?jiǎng)討B(tài)開(kāi)辟，那么這里就牽扯到數(shù)組開(kāi)多大的空間？要想知道數(shù)組開(kāi)多大的空間那么就需要知道二叉樹(shù)有多少個(gè)結(jié)點(diǎn)，因此我們首先要求出二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)。

#二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)?

關(guān)于如何求二叉樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)在這篇博文中有過(guò)介紹：二叉樹(shù)的鏈?zhǔn)浇Y(jié)構(gòu)

求二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的主要思想：左右子樹(shù)結(jié)點(diǎn)個(gè)數(shù) + 1

代碼演示：

/**
 * 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().
 */


//計(jì)算二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)
//節(jié)點(diǎn)個(gè)數(shù) = 左右子樹(shù)節(jié)點(diǎn)個(gè)數(shù) + 1（根節(jié)點(diǎn)）
int BTreeSize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return BTreeSize(root->left) 
         + BTreeSize(root->right) + 1;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
 
    *returnSize = BTreeSize(root);
    //創(chuàng)建數(shù)組
    //......
}

#將二叉樹(shù)結(jié)點(diǎn)的值保存在數(shù)組中?

先對(duì)二叉樹(shù)進(jìn)行前序遍歷：根節(jié)點(diǎn)、左子樹(shù)、右子樹(shù)，然后將根節(jié)點(diǎn)的值保存在數(shù)組中，再進(jìn)行左右子樹(shù)的遞歸，這里要注意的是：需要從外部傳進(jìn)來(lái)一個(gè)下標(biāo)的指針，如果在函數(shù)內(nèi)部設(shè)置下標(biāo)，那么每一次函數(shù)遞歸調(diào)用就會(huì)創(chuàng)建新的下標(biāo)，這樣子只能保存第一個(gè)結(jié)點(diǎn)，如果從外部傳的是地址，那么每一次函數(shù)遞歸調(diào)用就會(huì)去訪問(wèn)這塊地址，這樣就確保了不會(huì)重復(fù)保存。

完整代碼：

/**
 * 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().
 */


//計(jì)算二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)
//節(jié)點(diǎn)個(gè)數(shù) = 左右子樹(shù)節(jié)點(diǎn)個(gè)數(shù) + 1（根節(jié)點(diǎn)）
int BTreeSize(struct TreeNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    return BTreeSize(root->left) 
         + BTreeSize(root->right) + 1;
}

//前序遍歷
//將前序遍歷的結(jié)果保存在一個(gè)數(shù)組里面
void _preorderTraversal(struct TreeNode* root, int* pa, int* pi)
{
    //判斷是否為空樹(shù)
    if(root == NULL)
        return;
    //若不為空則將根節(jié)點(diǎn)保存至數(shù)組中
    pa[*pi] = root->val;
    (*pi)++;

    //繼續(xù)遞歸遍歷它的左右子樹(shù)
    _preorderTraversal(root->left, pa, pi);
    _preorderTraversal(root->right, pa, pi);
}


int* preorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize = BTreeSize(root);
    //創(chuàng)建數(shù)組
    //根據(jù)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)來(lái)創(chuàng)建數(shù)組的大小
    int* a = (int*)malloc(sizeof(int) * (*returnSize));
    //創(chuàng)建數(shù)組下標(biāo)
    int i = 0;
    _preorderTraversal(root, a, &i);
    //返回前序遍歷結(jié)果
    return a;
}

朋友們、伙計(jì)們，美好的時(shí)光總是短暫的，我們本期的的分享就到此結(jié)束，最后看完別忘了留下你們彌足珍貴的三連喔，感謝大家的支持！?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-539806.html

到了這里，關(guān)于二叉樹(shù)OJ題：LeetCode--144.二叉樹(shù)的前序遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！