遞歸法

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

int countNodes(TreeNoed* root)

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

if(node==nullptr) return 0;

3、確定單層遞歸的邏輯：先求它的左?樹的節(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 leftnodes=getnodes(node->left); //左int rightnodes=getnodes(node->right);//右int sum=leftnodes+rightnodes;//中return sum+1;

完整遞歸代碼：

class Solution { public:int getnodes(TreeNode* node){if(node==nullptr) return 0;int leftnodes=getnodes(node->left); //左int rightnodes=getnodes(node->right);//右int sum=leftnodes+rightnodes;//中return sum+1;}int countNodes(TreeNode* root) {return getnodes(root);} };

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(logn)，算上了遞歸系統(tǒng)棧占?的空間

迭代法

class Solution{ public:int countNodes(TreeNode* root){if(root==nullptr) return 0;queue<TreeNode*> que;que.push(root);int sum=0;while(!que.empty()){int size=que.size();for(int ii=0;ii<size;ii++){sum++;TreeNode* node=que.front();que.pop();if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return sum;} };

時(shí)間復(fù)雜度：O(n)空間復(fù)雜度：O(n)

利用完全二叉樹的性質(zhì)

完全二叉樹只有兩種情況：
1、滿二叉樹----->高度為h的滿二叉樹有 2^h-1 個(gè)結(jié)點(diǎn)。
2、最后?層葉?節(jié)點(diǎn)沒有滿。---->也就是說(shuō)如果整個(gè)樹不是滿二叉樹就分別遞歸其左右孩子，遞歸到一定深度一定會(huì)有左孩子或右孩子為滿二叉樹，然后可以按照滿二叉樹來(lái)計(jì)算節(jié)點(diǎn)個(gè)數(shù)。

class Solution{ public:int countNodes(TreeNode* root){if(root==nullptr) return 0;TreeNode* left=root->left;TreeNode* right=root->right;int leftHeight=0,rightHight=0;while(left){ //求左子樹的高度left=left->left; leftHeight++;}while(right){ //求右子樹的高度right=right->right; rightHeight++;}if(leftHeight==rightHeight){return (2<<leftHeight)-1; //2<<相當(dāng)于2^2 ,所以高度初始化為0 }//如果整棵樹不是滿二叉樹，就遞歸其左右孩子return countNodes(root->left)+countNodes(root->right)+1；} };

時(shí)間復(fù)雜度：O(logn * logn)
空間復(fù)雜度：O(logn)

總結(jié)

以上是生活随笔為你收集整理的完全二叉树的结点个数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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