給「代碼隨想錄」一個(gè)星標(biāo)吧！?

不管有多少個(gè)節(jié)點(diǎn)，大家中秋&&國慶快樂哈

?

如果之前兩篇二叉樹：看看這些樹的最大深度， 二叉樹：看看這些樹的最小深度都認(rèn)真看了的話，這道題目可以分分鐘刷掉了，愉快過節(jié)！

222.完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)

給出一個(gè)完全二叉樹，求出該樹的節(jié)點(diǎn)個(gè)數(shù)。

示例:

思路

這道題目其實(shí)沒有必要強(qiáng)調(diào)是完全二叉樹，就是求二叉樹節(jié)點(diǎn)的個(gè)數(shù)。

依然可以使用遞歸法和迭代法來解決。

這道題目的遞歸法和求二叉樹的深度寫法類似， 而迭代法：二叉樹層序遍歷模板稍稍修改一下，記錄遍歷的節(jié)點(diǎn)數(shù)量就可以了。

遞歸遍歷的順序依然是后序(左右中)。

遞歸

如果對求二叉樹深度還不熟悉的話，看這篇：二叉樹：看看這些樹的最大深度。

確定遞歸函數(shù)的參數(shù)和返回值：參數(shù)就是傳入樹的根節(jié)點(diǎn)，返回就返回以該節(jié)點(diǎn)為根節(jié)點(diǎn)二叉樹的節(jié)點(diǎn)數(shù)量，所以返回值為int類型。

代碼如下：

int?getNodesNum(TreeNode*?cur)?{

確定終止條件：如果為空節(jié)點(diǎn)的話，就返回0，表示節(jié)點(diǎn)數(shù)為0。

代碼如下：

if?(cur?==?NULL)?return?0;

確定單層遞歸的邏輯：先求它的左子樹的節(jié)點(diǎn)數(shù)量，再求的右子樹的節(jié)點(diǎn)數(shù)量，最后取總和再加一 (加1是因?yàn)樗闵袭?dāng)前中間節(jié)點(diǎn))就是目前節(jié)點(diǎn)為根節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量。

代碼如下：

int?leftNum?=?getNodesNum(cur->left);??????//?左
int?rightNum?=?getNodesNum(cur->right);????//?右
int?treeNum?=?leftNum?+?rightNum?+?1;??????//?中
return?treeNum;

所以整體C++代碼如下：

class?Solution?{
private:
????int?getNodesNum(TreeNode*?cur)?{
????????if?(cur?==?0)?return?0;
????????int?leftNum?=?getNodesNum(cur->left);??????//?左
????????int?rightNum?=?getNodesNum(cur->right);????//?右
????????int?treeNum?=?leftNum?+?rightNum?+?1;??????//?中
????????return?treeNum;
????}
public:
????int?countNodes(TreeNode*?root)?{
????????return?getNodesNum(root);
????}
};

代碼精簡之后C++代碼如下：

class?Solution?{
public:
????int?countNodes(TreeNode*?root)?{
????????if?(root?==?NULL)?return?0;
????????return?1?+?countNodes(root->left)?+?countNodes(root->right);
????}
};

迭代法

如果對求二叉樹層序遍歷還不熟悉的話，看這篇：二叉樹：層序遍歷登場！。

那么只要模板少做改動(dòng)，加一個(gè)變量result，統(tǒng)計(jì)節(jié)點(diǎn)數(shù)量就可以了

class?Solution?{
public:
????int?countNodes(TreeNode*?root)?{
????????queue?que;if?(root?!=?NULL)?que.push(root);
????????int?result?=?0;while?(!que.empty())?{
????????????int?size?=?que.size();for?(int?i?=?0;?i?????????????????TreeNode*?node?=?que.front();
????????????????que.pop();
????????????????result++;???//?記錄節(jié)點(diǎn)數(shù)量if?(node->left)?que.push(node->left);if?(node->right)?que.push(node->right);
????????????}
????????}return?result;
????}
};

總結(jié)

這道題目的解法其實(shí)我們在二叉樹：看看這些樹的最大深度和 二叉樹：看看這些樹的最小深度都有提到過了。

一樣的分析套路，代碼也差不多，估計(jì)此時(shí)大家最這一類求二叉樹節(jié)點(diǎn)數(shù)量以及求深度應(yīng)該非常熟練了。

沒有做過這道題目的同學(xué)可以愉快的刷了它。

最后祝大家中秋&&國慶節(jié)日愉快哈！

在留言區(qū)留下你的思路吧！

-------end-------

我將算法學(xué)習(xí)相關(guān)的資料已經(jīng)整理到了Github ：https://github.com/youngyangyang04/leetcode-master，里面還有l(wèi)eetcode刷題攻略、各個(gè)類型經(jīng)典題目刷題順序、思維導(dǎo)圖看一看一定會(huì)有所收獲，如果給你有幫助給一個(gè)star支持一下吧！

另外因?yàn)楣娞?hào)改版，時(shí)間線被打亂，一些精彩文章大家可能錯(cuò)過了。如果感覺這里的文章對你有幫助，趕緊給「代碼隨想錄」加一個(gè)星標(biāo)吧，方便第一時(shí)間閱讀文章。往期精彩回顧二叉樹：看看這些樹的最小深度二叉樹：看看這些樹的最大深度二叉樹：我對稱么？本周小結(jié)！(二叉樹)二叉樹：你真的會(huì)翻轉(zhuǎn)二叉樹么？二叉樹：層序遍歷登場！二叉樹：前中后序迭代方式的寫法就不能統(tǒng)一一下么？二叉樹：聽說遞歸能做的，棧也能做！二叉樹：一入遞歸深似海，從此offer是路人關(guān)于二叉樹，你該了解這些！「代碼隨想錄」期待你的關(guān)注！

每天8:35準(zhǔn)時(shí)推送一道經(jīng)典算法題目，推送的每道題目都不是孤立的，而是由淺入深，環(huán)環(huán)相扣，幫你梳理算法知識(shí)脈絡(luò)，輕松學(xué)算法！

刷題可以加我微信！右邊為個(gè)人微信，添加時(shí)備注：「簡單自我介紹」+「組隊(duì)刷題」我就知道你[在看]

總結(jié)

以上是生活随笔為你收集整理的完全二叉树最小深度_二叉树：我有多少个节点？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。