所有的LeetCode題解索引，可以看這篇文章——【算法和數(shù)據(jù)結(jié)構(gòu)】LeetCode題解。
一、題目
二、一般遍歷解法
??思路分析：利用層序遍歷，然后用num++記錄節(jié)點數(shù)量。其他的例如遞歸法和迭代法也是如此。
??層序遍歷程序如下：
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> que;
que.push(root);
int num = 0; // 節(jié)點數(shù)量
while (!que.empty()) {
int size = que.size(); // size必須固定, que.size()是不斷變化的
for (int i = 0; i < size; ++i) {
TreeNode* node = que.front();
que.pop();
num++;
if (node->left) que.push(node->left); // 空節(jié)點不入隊
if (node->right) que.push(node->right);
}
}
return num;
}
};
復雜度分析：
- 時間復雜度： O ( n ) O(n) O(n)。
-
空間復雜度：
O
(
n
)
O(n)
O(n)。
??遞歸程序如下（這應該是最精簡的版本了）：
class Solution2 {
public:
int countNodes(TreeNode* root) {
return root == NULL ? 0 : countNodes(root->left) + countNodes(root->right) + 1;
}
};
三、利用完全二叉樹性質(zhì)
??思路分析：完全二叉樹具有一個特性，假設它的深度為K，它的節(jié)點個數(shù)在
[
2
K
?
1
?
1
,
2
K
?
1
]
[2^{K-1}-1, 2^K-1]
[2K?1?1,2K?1]之間，意味著它只有兩種情況，一種是滿二叉樹，一種是最后一層葉子節(jié)點沒有滿。對于情況一可以用
2
K
?
1
2^K-1
2K?1來計算，對于情況二分別遞歸其左子樹和右子樹，遞歸到一定深度一定有左子樹或者右子樹為滿二叉樹，然后按照情況一來計算。那么滿二叉樹的最左邊節(jié)點和最右邊節(jié)點的深度一定是相等的，依據(jù)這個特性判斷子樹是否為滿二叉樹。
遞歸程序當中，我們要確定三個步驟，1、輸入?yún)?shù)，返回值 2、遞歸終止條件 3、單層遞歸邏輯。輸入?yún)?shù)為中間節(jié)點，返回值為左子樹的節(jié)點數(shù)量+右子樹節(jié)點數(shù)量+1（+1是加上中間節(jié)點）。當節(jié)點為空時，遞歸終止，返回0。每次遞歸我們都要計算最左/右邊節(jié)點深度，然后判斷二者是否相等，如果相等則是滿二叉樹，返回
2
K
?
1
2^K-1
2K?1，K為深度。程序當中使用了左移運算符，因為運算符的優(yōu)先級問題，記得加括號。左移運算符是二進制運算，計算機計算的更快。
??程序如下：
class Solution3 {
public:
// 利用完全二叉樹的性質(zhì)，遞歸法
int countNodes(TreeNode* root) {
if (!root) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int Ldepth = 0, Rdepth = 0;
while (left) { // 遞歸左子樹
left = left->left;
Ldepth++;
}
while (right) { // 遞歸右子樹
right = right->right;
Rdepth++;
}
if (Ldepth == Rdepth) {
return (2 << Ldepth) - 1; // <<為左移運算符（位運算符），相當于2*leftDepth，但二進制運算計算機算的更快
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
復雜度分析：文章來源：http://www.zghlxwxcb.cn/news/detail-608031.html
- 時間復雜度： O ( n ) O(n) O(n)。
- 空間復雜度： O ( n ) O(n) O(n)。
四、完整代碼
# include <iostream>
# include <vector>
# include <queue>
# include <string>
# include <algorithm>
using namespace std;
// 樹節(jié)點定義
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
// 層序遍歷法
int countNodes(TreeNode* root) {
if (!root) return 0;
queue<TreeNode*> que;
que.push(root);
int num = 0; // 節(jié)點數(shù)量
while (!que.empty()) {
int size = que.size(); // size必須固定, que.size()是不斷變化的
for (int i = 0; i < size; ++i) {
TreeNode* node = que.front();
que.pop();
num++;
if (node->left) que.push(node->left); // 空節(jié)點不入隊
if (node->right) que.push(node->right);
}
}
return num;
}
};
class Solution2 {
public:
int countNodes(TreeNode* root) {
return root == NULL ? 0 : countNodes(root->left) + countNodes(root->right) + 1;
}
};
class Solution3 {
public:
// 利用完全二叉樹的性質(zhì)，遞歸法
int countNodes(TreeNode* root) {
if (!root) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int Ldepth = 0, Rdepth = 0;
while (left) { // 遞歸左子樹
left = left->left;
Ldepth++;
}
while (right) { // 遞歸右子樹
right = right->right;
Rdepth++;
}
if (Ldepth == Rdepth) {
return (2 << Ldepth) - 1; // <<為左移運算符（位運算符），相當于2*leftDepth，但二進制運算計算機算的更快
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
void my_print(vector <string>& v, string msg)
{
cout << msg << endl;
for (vector<string>::iterator it = v.begin(); it != v.end(); it++) {
cout << *it << " ";
}
cout << endl;
}
void my_print2(vector<vector<int>>& v, string str) {
cout << str << endl;
for (vector<vector<int>>::iterator vit = v.begin(); vit < v.end(); ++vit) {
for (vector<int>::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {
cout << *it << ' ';
}
cout << endl;
}
}
// 前序遍歷迭代法創(chuàng)建二叉樹，每次迭代將容器首元素彈出（彈出代碼還可以再優(yōu)化）
void Tree_Generator(vector<string>& t, TreeNode*& node) {
if (t[0] == "NULL" || !t.size()) return; // 退出條件
else {
node = new TreeNode(stoi(t[0].c_str())); // 中
t.assign(t.begin() + 1, t.end());
Tree_Generator(t, node->left); // 左
t.assign(t.begin() + 1, t.end());
Tree_Generator(t, node->right); // 右
}
}
// 層序遍歷
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size(); // size必須固定, que.size()是不斷變化的
vector<int> vec;
for (int i = 0; i < size; ++i) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left); // 空節(jié)點不入隊
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
int main()
{
vector<string> t = { "1", "2", "4", "NULL", "NULL", "5", "NULL", "NULL", "3", "6", "NULL", "NULL", "NULL"}; // 前序遍歷
my_print(t, "目標樹");
TreeNode* root = new TreeNode();
Tree_Generator(t, root);
vector<vector<int>> tree = levelOrder(root);
my_print2(tree, "目標樹:");
Solution2 s1;
int result = s1.countNodes(root);
cout << "節(jié)點數(shù)量為：" << result << endl;
system("pause");
return 0;
}
end文章來源地址http://www.zghlxwxcb.cn/news/detail-608031.html
到了這里，關(guān)于【算法與數(shù)據(jù)結(jié)構(gòu)】222、LeetCode完全二叉樹的節(jié)點個數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
